什么是时间复杂度，如何找到时间复杂度？[副本]

Question

我已经阅读了这么多的资源，但仍然无法理解什么是时间复杂性。我阅读的参考资料基于各种公式，我理解O(n)用于表示时间复杂性，但我不知道如何表示。谁能请解释这个原则，以一个可以理解的明确的方式请给我。

Answer 1

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

我发现了一篇关于如何计算任何算法或程序的时间复杂度的好文章

计算时间复杂度最常用的度量是大O表示法。这去掉了所有的常数因素，以便当N接近无穷大时，可以根据N估计运行时间。一般来说，您可以这样想：

statement;

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

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

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

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

一般情况下，用一维的每一项做某事是线性的，用二维的每一项做某事是二次的，把工作区域分成两半是对数的。还有其他大O度量，如立方、指数和平方根，但它们并不常见。大O表示法被描述为O（），其中是度量值。快速排序算法可以描述为O(N*log(N))。

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

编辑：

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

方程为:n/2^k=1。由于2^logn=n，我们得到k=logn。因此，该算法需要的迭代次数为O(logn)，这将使该算法O(nlogn)

此外，大O符号给出了一个易于计算的平台无关的近似，即算法如何渐近（在无穷远处）表现，它可以将算法的“族”划分为它们复杂度的子集，并让我们容易地比较它们之间的复杂性。