算法的时间和空间复杂度分析

什么是算法？

在计算机科学中，每当我们要解决一些计算问题时，我们都会定义一组解决该问题需要遵循的步骤。这些步骤统称为算法。

如何区分算法的好坏？

针对特定问题可以有很多算法。那么，如何区分算法的好坏呢？

让我们了解一个好的算法的属性：

正确性：如果算法对于每组输入都以正确的输出停止运行，则该算法被认为是正确的。如果没有为任何特定的输入集获得正确的输出，则你的算法是错误的。
有限性：通常，人们会忽略这一点，但这是算法评估中的重要因素之一。该算法必须始终在有限数量的步骤后终止。例如，在递归和循环的情况下，你的算法应终止，否则最终将分别产生堆栈溢出和无限循环的情况。
效率：始终使用高效算法。效率一词是指：
1. 该算法应有效地使用系统可用的资源。
2. 计算时间（生成对应于特定输入的输出所花费的时间）应尽可能短。
3. 算法使用的内存也应尽可能少。通常，在计算时间和内存之间需要权衡。因此，我们需要确定时间是否比空间重要，反之亦然，然后相应地编写算法。

因此，我们已经看到了可用于评估算法的三个因素。在这三个因素中，最重要的因素是算法的效率。

算法效率

算法的效率主要由两个因素定义，即空间和时间。一种好的算法是占用更少的时间和更少的空间，但是不可能一直这样。在时间和空间之间需要权衡。如果要减少时间，则空间可能会增加。同样，如果要减少空间，则时间可能会增加。因此，你必须在空间或时间上妥协。让我们进一步了解算法的时空复杂度。

空间复杂度

算法的空间复杂度表示对于各种输入大小，算法用于其工作所使用或需要的总空间。例如：

1
2
3

List list = new ArrayList();
for(int i = 0; i < n; i++)
    list.add(i);

在上面的示例中，我们正在循环向列表中加入数据。因此，上述代码的空间复杂度约为“ n”，即，如果n增加，则空间需求也将相应增加。

即使在创建变量时，也需要一些空间来运行算法。算法所需的所有空间统称为算法的空间复杂度。

时间复杂度

时间复杂度是算法针对输入大小执行的用于完成其任务的操作数（考虑到每个操作花费相同的时间量）。以最少数量的操作执行任务的算法被认为是效率最高的算法。

时间复杂度是指执行这个算法所需要的计算工作量，其复杂度反映了程序执行时间「随输入规模增长而增长的量级」，在很大程度上能很好地反映出算法的优劣与否。一个算法花费的时间与算法中语句的「执行次数成正比」，执行次数越多，花费的时间就越多。一个算法中的执行次数称为语句频度或时间频度，记为T(n)，其中n称为问题的规模，当n不断变化时，它所呈现出来的规律，我们称之为时间复杂度。比如：T(n) = 3n^2与 T(n) = 5n^23n，虽然算法的时间频度不一样，但他们的时间复杂度却是一样的，*「时间复杂度只关注最高数量级，且与之系数也没有关系」**。

算法所花费的时间还取决于你所使用的系统的计算速度，但是我们忽略了这些外部因素，并且仅考虑相对于输入大小，执行特定语句的次数。假设执行一条语句需要的时间为1秒，那么执行n条语句要花费的时间为n秒。

假设你遇到一个问题，并且针对同一问题编写了三种算法。现在，你需要从这三种算法中选择一种。你会怎么做？

你可以做的一件事就是在三台不同的计算机上运行所有三种算法，提供相同的输入，找到所有三种算法所花费的时间，然后选择花费最少时间的一种。可以吗不，所有系统都可能使用某些不同的处理器。因此，处理速度可能会有所不同。因此，我们不能使用这种方法来找到最有效的算法。
你可以做的另一件事是在同一台计算机上运行这三种算法，并尝试找出算法花费的时间并选择最佳的时间。但是在这里，你可能会得到错误的结果，因为在执行程序时，还有其他与你的程序一起执行的事情，因此你可能会获得错误的时间。

注意：此处要注意的一件事是，我们正在查找同一输入的不同算法所花费的时间，因为如果我们更改输入，那么与效率较低的算法相比，有效的算法可能会花费更多的时间，因为输入大小两种算法都不同。

因此，我们已经看到，无法通过计算在特定系统中执行算法所花费的时间来判断算法。我们需要一些标准的符号来分析算法。我们使用渐近符号来分析任何算法，并在此基础上找到最有效的算法。在这里，以渐近符号表示，我们不考虑系统配置，而是考虑输入的增长顺序。我们尝试找出在增加/减少输入大小之后算法所花费的时间或空间将如何增加/减少。

有三种渐近符号用于表示算法的时间复杂度。他们是：

Θ记号（theta）
大O表示法
Ω表示法

在了解这三种渐近符号之前，我们应该了解算法的最佳，平均和最差情况。

最佳情况，平均情况和最坏情况

对于不同的输入，算法可以具有不同的时间。某些输入可能需要1秒，其他输入可能需要10秒。

例如：我们有一个名为“ arr”的*数组和一个整数“ *k ”。我们需要查找数组“ arr ”中是否存在整数“ k ” ？如果整数存在，则返回1，其他返回0。尝试为该问题创建算法。

可以从上述问题中提取以下信息：

输入：这里的输入是一个大小为n的整数数组，我们需要在该数组中搜索一个整数k。
输出：如果在数组中找到元素“ k”，则返回1，否则返回0。

现在，上述问题的一种可能解决方案是线性搜索，即遍历数组的每个元素，并将该元素与“ k”进行比较。如果等于“ k”，则返回1，否则，继续比较数组中的更多元素，如果到达数组的末尾却没有找到任何元素，则返回0。

/**
   * @param arr integer 数组
   * @param n 数组长度
   * @param k 要查找的值
   */
  public static int searchK(int arr[], int n, int k){
      for (int i = 0; i < n; i++) {
          if (arr[i] == k)
              return 1;
      }
      return 0;
  }

分析上述代码

i = 0 执行一次
i < n 执行 n+1 次
i++ 执行 n 次
if(arr[i] == k) 执行 n 次(如果”k”没在数组里)
return 1 执行 1 次(如果”k”在数组里)
return 0 执行 1 次(如果”k”没在数组里)

代码中的每个语句都需要固定的时间，我们设花费的时间为“ C”。因此，无论何时声明一个整数，更改某些整数或其他变量的值都需要花费固定时间，而比较两个变量也需要花费固定时间。因此，如果一条语句花费的时间为“ C”，而执行了“ N”次，则它将花费C * N的时间。现在，考虑一下我们刚刚编写的上述算法的以下输入：

注意：这里我们假设每个语句要花费1秒的时间来执行。

如果输入数组为[1、2、3、4、5]，并且你想查找数组中是否存在“ 1”，则代码的 if 条件将执行1次，并找到元素1在数组中。因此，此处的if条件将花费1秒。
如果输入数组为[1、2、3、4、5]，并且你想查找数组中是否存在“ 3”，则代码的 if 条件将执行3次，并找到元素3在数组中。因此，此处的if条件将花费3秒。
如果输入数组为[1、2、3、4、5]，并且你想查找数组中是否存在“ 6”，则代码的 if 条件将执行5次，并找到数组中元素6不存在，在这种情况下算法将返回0。因此，此处的if条件需要5秒钟。

如你所见，对于相同的输入数组，对于“ k”的不同值，我们具有不同的时间。因此，这可以分为三种情况：

最佳情况：这是算法运行时间的下限。我们必须知道导致最少数量的操作执行的情况。在上面的示例中，我们的数组为[1、2、3、4、5]，我们正在查找数组中是否存在“ 1”。因此，在这里，仅需进行一次比较，你就会知道你的元素存在于数组中。因此，这是算法的最佳情况。
平均情况：我们计算所有可能输入的运行时间，将所有计算出的值相加，然后将总和除以输入总数。我们必须知道（或预测）案件的分布。
最坏的情况：这是算法运行时间的上限。我们必须知道导致最大数量的操作执行的情况。在我们的示例中，最坏的情况是给定的数组为[1、2、3、4、5]，然后尝试查找数组中是否存在元素“ 6”。此处，循环的if条件将执行5次，然后算法将给出“ 0”作为输出。

因此，我们了解了算法的最佳，平均和最差情况。现在，让我们回到渐近符号中，我们看到我们使用三种渐进符号来表示算法的复杂性，即Θ表示法（theta），Ω表示法，Big O表示法。

注意：在渐进分析中，我们通常处理较大的输入量。

Θ记号（theta）

Θ符号用于查找算法的平均界限，即它定义了上限和下限，你的算法将位于这些级别之间。

Ω表示法

Ω表示算法的下限，即算法花费的时间不能低于此时间。换句话说，这是算法返回结果的最快时间。提供最佳情况输入时，算法花费的时间。

大O表示法

大O表示法定义了任何算法的上限，即算法所花费的时间不能超过此时间。换句话说，我们可以说大O表示法表示算法花费的最大时间或算法的最坏情况下的时间复杂度。因此，对于算法的时间复杂度而言，大O表示法是最常用的表示法。

如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。空间复杂度同理。举个例子，令 f(n) = 2n^2✖️3n，O(f(n)) = O(2n^2 ✖️n)=O(n^2)。

原文链接: https://afteracademy.com/blog/time-and-space-complexity-analysis-of-algorithm