算法的时间复杂度

原文：https://www.studytonight.com/data-structures/time-complexity-of-algorithms

对于任何已定义的问题，可以有 N 个解。总的来说是这样的。如果我有问题，我和我所有的朋友讨论这个问题，他们都会给我建议不同的解决方案。我必须根据情况决定哪种解决方案是最好的。

同样，对于任何必须用程序来解决的问题，可以有无限多种解决方案。让我们举一个简单的例子来理解这一点。下面我们有两种不同的算法来求一个数的平方(有一段时间，忘记任何数的平方n都是n*n):

这个问题的一个解决方案可以是，运行一个循环n次，从数字n开始，每次加上n。

/* 
    we have to calculate the square of n
*/
for i=1 to n
    do n = n + n
// when the loop ends n will hold its square
return n

或者，我们可以简单地用一个数学运算符*来求平方。

/* 
    we have to calculate the square of n
*/
return n*n

在上面两个简单的算法中，您看到了一个问题如何可以有多个解决方案。第一个解决方案需要一个循环来执行n次，而第二个解决方案使用一个数学运算符*来返回一行中的结果。那么哪一个是更好的方法，当然是第二个。

什么是时间复杂度？

算法的时间复杂度表示程序运行到完成所需的总时间。

算法的时间复杂度最常用大 O 符号来表示。这是表示时间复杂度的渐近符号。我们将在下一个教程中详细研究它。

时间复杂度通常通过计算任何算法完成执行的基本步骤数来估计。就像上面的例子一样，对于第一个代码，循环将运行n次，因此时间复杂度至少为n，并且随着n值的增加，所花费的时间也将增加。而对于第二个代码，时间复杂度是不变的，因为它永远不会依赖于n的值，它总是以 1 步给出结果。

由于算法的性能可能随着不同类型的输入数据而变化，因此对于算法，我们通常使用算法的最坏情况时间复杂度，因为这是任何输入大小所花费的最大时间。

计算时间复杂度

现在让我们进入下一个与时间复杂度相关的大主题，即如何计算时间复杂度。有时候会变得很混乱，但我们会试着用最简单的方式来解释。

现在计算时间复杂度最常用的度量是大 O 表示法。这去除了所有的恒定因素，以便当 N 接近无穷大时，可以相对于 N 估计运行时间。一般来说，你可以这样想:

statement;

以上我们有一个单一的声明。它的时间复杂度将是常量。语句的运行时间不会因 n 而改变

for(i=0; i < N; i++)
{
    statement;
}

上述算法的时间复杂度将为线性。循环的运行时间与 N 成正比，当 N 翻倍时，运行时间也翻倍。

for(i=0; i < N; i++) 
{
    for(j=0; j < N;j++)
    { 
    statement;
    }
}

这一次，上述代码的时间复杂度将是二次。两个循环的运行时间与 N 的平方成正比，当 N 翻倍时，运行时间增加 N * N。

while(low <= high) 
{
    mid = (low + high) / 2;
    if (target < list[mid])
        high = mid - 1;
    else if (target > list[mid])
        low = mid + 1;
    else break;
}

这是一种将一组数字分成两半的算法，用于搜索特定的字段(我们将在后面详细研究)。现在，这个算法将有一个对数时间复杂度。算法的运行时间与 N 可以除以 2 的次数成正比(这里 N 为高低)。这是因为算法每次迭代都会将工作区域分成两半。

void quicksort(int list[], int left, int right)
{
    int pivot = partition(list, left, right);
    quicksort(list, left, pivot - 1);
    quicksort(list, pivot + 1, right);
}

把前面的算法往前推，上面我们有一个快速排序的小逻辑(这个我们后面会详细研究)。现在在快速排序中，我们每次都将列表分成两半，但是我们重复迭代 N 次(其中 N 是列表的大小)。因此时间复杂度将是 N*log( N ) 。运行时间由 N 个对数循环(迭代或递归)组成，因此该算法是线性和对数的组合。

注:一般情况下，一维每一项做一件事是线性的，二维每一项做一件事是二次的，把工作区域对半划分是对数的。

时间复杂度的符号类型

Now we will discuss and understand the various notations used for Time Complexity.

  1. 大哦表示“少于或等于”<表达>迭代。
  2. 大ω表示“大于或等于”<表达式>迭代。
  3. 大θ表示“同”<表达>迭代。
  4. 小 Oh 表示“比”<表达式>迭代次数少。
  5. 小欧米茄表示多于<表示>迭代。

用例子理解时间复杂度的符号

O(表达式)是比表达式增长更慢或以相同速度增长的一组函数。它表示算法对所有输入值要求的最大值。它代表了算法时间复杂度的最坏情况。

Omega(表达式)是比表达式增长更快或以相同速度增长的一组函数。它表示算法对所有输入值所需的最短时间。它代表了算法时间复杂度的最佳情况。

θ(表达式)由位于 0(表达式)和ω(表达式)中的所有函数组成。它表示算法的平均界限。它代表算法时间复杂度的平均情况。

假设你已经计算出一个算法需要 f(n)次运算，其中，

f(n) = 3*n^2 + 2*n + 4\.   // n^2 means square of n

由于该多项式的增长速度与n2T3 相同，因此可以说函数 f 位于集合θ(n2)中。(同样的道理也存在于 O(n 2 ) 和欧米茄(n 2 ) 这两套里面。)

最简单的解释就是，因为θ表示和这个表达是一样的。因此，当 f(n) 以 n 2 的因子增长时，时间复杂度可以最好地表示为θ(n2)。

既然我们已经学习了算法的时间复杂度，那么你也应该学习一下算法的空间复杂度及其重要性。