什么是时间复杂度以及如何找到它？

Question

我已经阅读了很多资源，但仍然坚持了解时间的复杂性。我阅读的资源是基于各种公式的，我理解这O(n)是用来表示时间复杂度的，但是我不知道如何。任何人都可以以一种可以理解的清晰方式向我解释这个原则。

Answer 1

参考：如何计算时间复杂度算法

我找到了一篇与 如何计算任何算法或程序的时间复杂度* 有关的好文章 *

计算时间复杂度最常用的指标是Big 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的次数成正比。这是因为该算法在每次迭代中将工作区域划分为一半。

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 * log（N）。 运行时间由N个对数的循环（迭代或递归）组成，因此该算法是线性和对数的组合。

通常，对一维中的每个项目执行某项操作是线性的，对二维中每一个项目执行某项操作是二次项，并且将工作区域分为两半是对数的。还有其他Big
O度量，例如立方，指数和平方根，但它们并不那么普遍。大O表示法描述为O（），这里是小数位。快速排序算法将描述为 O（N * log（N））。

请注意，所有这些都未考虑最佳，平均和最坏情况下的度量。每个都有自己的Big O表示法。另请注意，这是一个非常简单的解释。Big
O是最常见的，但我已经展示过它更复杂。还有其他符号，例如大欧米茄，小o和大theta。在算法分析课程之外，您可能不会遇到它们。;）

编辑：

现在的问题是如何log n进入方程式：

1. 对于每一步，您在上半部分和下半部分递归调用算法。
2. 因此-所需的步骤总数是，如果您将问题每一步以2表示，则从n达到1所需的次数。

等式为：n / 2 ^ k =1。由于2 ^ logn = n，我们得到k =
logn。所以算法需要的迭代次数是O（logn），这会使算法O(nlogn)

同样， 大O 表示法使我们易于计算-
算法在渐近时（无穷大）如何表现出平台无关的近似值，可以将算法的“族”划分为复杂度的子集，并让我们轻松地比较它们之间的差异。