问题
如何找到一个算法的时间复杂度?
**我在SO上发布问题之前做了什么?
但我在哪里都找不到关于如何计算时间复杂性的清晰而直接的解释。
**我知道什么呢?
比方说,对于像下面这样简单的代码。
char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time
比如说像下面这样的一个循环。
for (int i = 0; i < N; i++) {
Console.Write('Hello World !');
}
int i=0;这将只执行**次。
时间实际上是计算到i=0
而不是声明。
i < N; 这将被执行N+1次
i++;这将被执行N次
因此,这个循环所需的操作数是
{1+(n+1)+n}=2n+2
注:这仍然可能是错误的,因为我对计算时间复杂度的理解没有信心。
**我想知道的是什么?
好吧,这些小的基本计算我想我知道,但在大多数情况下,我看到的时间复杂性为
O(N), O(n2), O(log n), O(n!).... 和许多其他。
有谁能帮助我理解如何计算一个算法的时间复杂度?我相信有很多像我这样的新手都想知道这个问题。
下面的答案是从上面复制的(以防止优秀的链接失效)。
计算时间复杂度的最常用指标是大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符号。还要注意的是,这是个非常简单的解释。大O是最常见的,但它也更复杂,我已经展示了。还有其他一些符号,如大OMEGA、小O和大Theta。你可能不会在算法分析课程之外遇到它们。)
如何找到算法的时间复杂度
你把它将执行多少条机器指令作为其输入大小的函数加起来,然后把表达式简化为最大的(当N非常大时)项,并可以包括任何简化常数因子。
例如,让我们看看如何简化2N + 2
机器指令,将其描述为仅仅O(N)
。
**为什么我们要去掉两个 "2"?
我们对N变大时算法的性能感兴趣。
考虑一下2N和2这两个项。
当N变大时,这两个项的相对影响是什么?假设N是一百万。
那么第一个项是200万,第二个项只有2。
由于这个原因,对于大的N,除了最大的项之外,我们放弃所有的项。
所以,现在我们已经从2N + 2
变成了2N
。
传统上,我们只对性能感兴趣直到恒定系数。
这意味着我们并不关心N大时是否有一些常数倍的性能差异。 反正2N的单位首先是不好定义的。 因此,我们可以乘以或除以一个恒定系数来得到最简单的表达。
所以2N
就变成了N
。
O(n)是用于书写算法的时间复杂性的大O符号。当你把一个算法的执行次数加起来时,你会得到一个类似于2N+2的表达式,在这个表达式中,N是主导项(如果它的值增加或减少,对表达式影响最大的项)。现在O(N)是时间上的灵活性,而N是主导项。 例子
For i= 1 to n;
j= 0;
while(j<=n);
j=j+1;
这里内循环的总执行次数为n+1,外循环的总执行次数为n(n+1)/2,所以整个算法的总执行次数为n+1+n(n+1/2) = (n^2+3n)/2。 这里n^2是主导项,所以这个算法的时间复杂度是O(n^2)