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

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指标,如立方,指数和平方根,但它们并不常见.Big 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符号使我们易于计算 - 平台无关近似算法将如何渐近地(在无穷大处)行为,这可以将算法的"族"划分为其复杂性的子集,并让我们在它们之间轻松比较.

您还可以查看此问题以获得更多阅读:使用递归方程的程序的时间复杂度