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

Question

<分区>

Answer 1

引用:How to Calculate Time complexity algorithm

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

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

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 符号。另请注意，这是一个非常简单的解释。大 O 是最常见的，但它也比我展示的更复杂。还有其他符号，例如 big omega、little o 和 big theta。在算法分析类(class)之外，您可能不会遇到它们。 ;)

编辑:

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

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

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

此外，big O 表示法让我们更容易计算 - 平台无关的近似算法将如何渐进(在无穷大)，它可以将算法的“家族”分成其复杂性的子集, 让我们轻松地比较它们。

您还可以查看此问题以进行更多阅读:Time complexity of the program using recurrence equation