9

我已经阅读了很多资源，但仍然无法理解时间复杂度是什么。我阅读的资源是基于各种公式的，我知道这O(n)是用来表达时间复杂度的，但我不知道如何。谁能以一种可以理解的清晰方式向我解释这个原则。

4

2 回答 2

34

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

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

计算时间复杂度的最常用指标是大 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 个循环（迭代或递归）组成，因此该算法是线性和对数的组合。

一般来说，对一维中的每个项目做某事是线性的，对二维中的每个项目做某事是二次的，将工作区域分成两半是对数的。还有其他大 O 度量，例如三次、指数和平方根，但它们并不常见。大 O 表示法被描述为 O ( ) 其中是度量。快速排序算法将被描述为O ( N * log ( N ) )。

请注意，这些都没有考虑到最佳、平均和最坏情况的措施。每个都有自己的大 O 符号。另请注意，这是一个非常简单的解释。Big O 是最常见的，但也比我展示的更复杂。还有其他符号，例如大 omega、小 o 和大 theta。您可能不会在算法分析课程之外遇到它们。;)

编辑：

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

  1. 对于每一步，您在前半部分和后半部分递归地调用算法。
  2. 因此 - 所需的步骤总数是如果您将问题每一步除以 2 所需要的从 n 到 1 的次数。

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

此外，大 O表示法使我们易于计算 - 与平台无关的近似算法将如何渐近（在无穷大处）表现，这可以将算法的“家族”划分为其复杂性的子集，让我们轻松地在它们之间进行比较。

您还可以查看此问题以获取更多信息：使用递归方程的程序的时间复杂度

于 2013-04-26T09:13:28.717 回答
2

您还应该阅读一下Amortized Analysis以完全理解时间复杂度的概念。摊销分析用于通过考虑所有操作来确定算法性能的最坏情况界限。

维基百科文章的链接如下，

http://en.wikipedia.org/wiki/Amortized_analysis

于 2013-04-26T10:21:40.767 回答