如何findalgorithm的时间复杂度

问题

如何findalgorithm的时间复杂度？

在SO上发布问题之前我做了什么？

我已经通过这个，这个和其他许多环节

但是，没有我能够find一个明确和直接的解释如何计算时间复杂性。

我知道什么？

说一个简单的代码如下所示：

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而不是声明。

我<N; 这将被执行N + 1次

我++; 这将被执行N次

所以这个循环所需的操作数量是

{1+（N + 1）+ N} = 2N + 2

注意：这仍然可能是错误的，因为我对计算时间复杂度的理解没有把握

我想知道什么？

好吧，我想我知道这些小的基本计算，但在大多数情况下，我已经看到了时间的复杂性

O（N），O（n2），O（log n），O（n！） ….等等，

谁能帮我理解一个algorithm的时间复杂度？我确信有很多像我这样想知道的新手。

如何findalgorithm的时间复杂度

将它将执行的机器指令数量与其input大小相加，然后将expression式简化为最大（当N非常大时）项，并且可以包括任何简化常数因子。

例如，让我们看看我们如何简化2N + 2机器指令来描述这只是O(N) 。

为什么我们删除两个2 ？

当N变大时，我们对algorithm的性能感兴趣。

考虑两个术语2N和2。

N变大时这两个项的相对影响是多less？假设N是一百万。

那么第一届是200万，第二届只有2年。

出于这个原因，我们放弃了大N的所有最大的条件。

所以，现在我们已经从2N + 2变成了2N 。

传统上，我们只对性能持续关注 。

这意味着当N很大的时候，我们并不关心在性能上是否存在一定的差异倍数。无论如何，2N的单位并不是很清楚。所以我们可以乘以或除以一个常数因子来达到最简单的expression式。

所以2N变成了N

这是一篇优秀的文章： http : //www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

下面的答案是从上面复制（如果优秀的链接崩溃）

计算时间复杂度的最常用指标是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; }

是对数的。 algorithm的运行时间与N可以除以2的次数成正比。这是因为该algorithm在每次迭代中将工作区域分成两半。

 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个循环（迭代或recursion）组成，因此该algorithm是线性和对数的组合。

一般情况下，一个维度上的每个项目都是线性的，二维中的每个项目都是二次的，而将工作区域分成两半是对数的。还有其他的大O措施，如立方，指数和平方根，但它们并不普遍。大O符号被描述为O（）其中是度量。快排algorithm将被描述为O（N * log（N））。

请注意，这些都没有考虑到最好的，平均的和最坏的情况。每个人都有自己的大O符号。另外请注意，这是一个非常简单的解释。大O是最常见的，但是我显示的也更加复杂。还有其他的符号，如大欧米茄，小o和大θ。在algorithm分析课程之外你可能不会遇到它们。 ;）

从这里摘录 – 介绍algorithm的时间复杂度

1.介绍

在计算机科学中，algorithm的时间复杂度量化algorithm作为代表input的string长度的函数运行的时间量。

2.大O符号

algorithm的时间复杂度通常用大O符号表示，不包括系数和低阶项。当用这种方式表示时，时间复杂度被认为是渐进地描述的，也就是说，随着input大小变为无穷大。

例如，如果一个algorithm对所有n的input所需的时间至多为5n ³ + 3n，则渐近时间复杂度为O（n ³ ）。稍后更多。

几个例子：

1 = O（n）
n = O（n ² ）
log（n）= O（n）
2 n + 1 = O（n）

3. O（1）恒定时间：

如果algorithm需要相同的时间而不pipeinput大小如何，algorithm被认为是在恒定的时间内运行的。

例子：

数组：访问任何元素
固定大小的堆栈：推送和popup方法
固定大小的队列：入队和出队方法

4. O（n）线性时间

如果algorithm的时间执行与input大小成正比，则algorithm被称为以线性时间运行，即随着input大小的增加，时间线性地增长。

考虑下面的例子，下面我直线地search一个元素，这有一个O（n）的时间复杂度。

 int find = 66; var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 }; for (int i = 0; i < numbers.Length - 1; i++) { if(find == numbers[i]) { return; } }

更多示例：

数组：线性search，遍历，查找最小等
ArrayList：包含方法
队列：包含方法

5. O（log n）对数时间：

如果algorithm的时间执行与input大小的对数成比例，则algorithm被称为在对数时间运行。

示例：二进制search

回想“二十问题”游戏 – 任务是在一个区间内猜测一个隐藏号码的值。每次猜测，你都会被告知你的猜测是太高还是太低。二十个问题的游戏意味着一个策略，使用你的猜测数量减半区间大小。这是解决二进制search的一般问题解决方法的一个例子

6. O（n2）二次时间

如果algorithm的时间执行与input大小的平方成正比，则algorithm被称为以二次方式运行。

例子：

泡沫sorting
selectsorting
插入sorting

7.一些有用的链接

大O的误解
确定algorithm的复杂性
大O备忘录

虽然这个问题有一些很好的答案。我想用loop几个例子给出另一个答案。

O（n） ：时间如果循环variables增加/减less一个常量，循环的复杂性被认为是O（n） 。例如，以下函数具有O（n）时间复杂度。

 // Here c is a positive integer constant for (int i = 1; i <= n; i += c) { // some O(1) expressions } for (int i = n; i > 0; i -= c) { // some O(1) expressions }

O（n ^ c） ：嵌套循环的时间复杂度等于内部语句执行的次数。例如，以下示例循环具有O（n ^ 2）时间复杂度
```
 for (int i = 1; i <=n; i += c) { for (int j = 1; j <=n; j += c) { // some O(1) expressions } } for (int i = n; i > 0; i += c) { for (int j = i+1; j <=n; j += c) { // some O(1) expressions } 
```
例如selectsorting和插入sorting具有O（n ^ 2）时间复杂度。
O（Logn）时间如果循环variables被划分/乘以常量，则循环的复杂性被视为O（Logn） 。
```
 for (int i = 1; i <=n; i *= c) { // some O(1) expressions } for (int i = n; i > 0; i /= c) { // some O(1) expressions } 
```
例如，二进制search具有O（Logn）时间复杂度。

O（LogLogn）时间如果循环variables以指数forms减less/增加一个常量，则循环的复杂性被视为O（LogLogn） 。

 // Here c is a constant greater than 1 for (int i = 2; i <=n; i = pow(i, c)) { // some O(1) expressions } //Here fun is sqrt or cuberoot or any other constant root for (int i = n; i > 0; i = fun(i)) { // some O(1) expressions }

时间复杂度分析的一个例子

 int fun(int n) { for (int i = 1; i <= n; i++) { for (int j = 1; j < n; j += i) { // Some O(1) task } } }

分析：

For i = 1, the inner loop is executed n times. For i = 2, the inner loop is executed approximately n/2 times. For i = 3, the inner loop is executed approximately n/3 times. For i = 4, the inner loop is executed approximately n/4 times. ……………………………………………………. For i = n, the inner loop is executed approximately n/n times.

所以上述algorithm的总时间复杂度为(n + n/2 + n/3 + … + n/n) ，成为n * (1/1 + 1/2 + 1/3 + … + 1/n)

关于系列(1/1 + 1/2 + 1/3 + … + 1/n)的重要事项等于O（Logn） 。所以上面代码的时间复杂度是O（nLogn） 。

参考： 1 2 3

时间复杂的例子

1 – 基本操作（算术，比较，访问数组的元素，赋值）：运行时间总是恒定的O（1）

例如：

 read(x) // O(1) a = 10; // O(1) a = 1.000.000.000.000.000.000 // O(1)

2 – 如果其他语句：只从两个或更多可能的语句中获取最大运行时间。

例：

 age = read(x) // (1+1) = 2 if age < 17 then begin // 1 status = "Not allowed!"; // 1 end else begin status = "Welcome! Please come in"; // 1 visitors = visitors + 1; // 1+1 = 2 end;

所以，上述伪代码的复杂度是T（n）= 2 + 1 + max（1,1 + 2）= 6，所以它的大哦仍然是常数T（n）= O（1）。

3 – 循环（for，while，repeat）：此语句的运行时间是循环次数乘以循环中的操作次数。

例：

 total = 0; // 1 for i = 1 to n do begin // (1+1)*n = 2n total = total + i; // (1+1)*n = 2n end; writeln(total); // 1

所以它的复杂度是T（n）= 1 + 4n + 1 = 4n + 2。因此，T（n）= O（n）。

4 – 嵌套循环（循环内部循环）：由于主循环内部至less有一个循环，所以此语句的运行时间使用O（n ^ 2）或O（n ^ 3）。

例：

 for i = 1 to n do begin // (1+1)*n = 2n for j = 1 to n do begin // (1+1)n*n = 2n^2 x = x + 1; // (1+1)n*n = 2n^2 print(x); // (n*n) = n^2 end; end;

常见运行时间

分析algorithm时有一些常见的运行时间：

O（1） – 恒定时间恒定时间是指运行时间恒定， 不受input大小的影响 。
O（n） – 线性时间当algorithm接受n个input大小时，它也会执行n个操作。
O（log n） – 运行时间为O（log n）的对数时间algorithm略快于O（n）。通常，algorithm将问题划分为相同大小的子问题。例如：二分查找algorithm，二进制转换algorithm。
O（n log n） – 线性时间这个运行时间经常在“分而治之algorithm”中find，它将recursion地将问题分解成子问题，然后在n次合并它们。示例：合并sortingalgorithm。
O（n ² ） – 二次时间看泡泡sortingalgorithm！
O（n ³ ） – 立方时间它与O（n ² ）具有相同的原理。
O（2 ⁿ ） – 指数时间当input变大时非常慢，如果n = 1000.000，T（n）将是21000.000。蛮力algorithm有这个运行时间。
O（n！） – 阶乘时间最慢！示例：旅行推销员问题（TSP）

从这篇文章采取。很好的解释应该给读一读。

大体来说，时间复杂度是一种总结随着input大小的增加algorithm的运行次数或运行时间如何增长的方法。

像生活中的大多数事情一样，鸡尾酒会可以帮助我们理解。

上）

当你到达聚会时，你必须摇动每个人的手（对每个项目进行操作）。随着参加者人数的增加，每个人握手的时间/工作量将增加为O(N) 。

为什么O(N)而不是cN ？

与人握手所花费的时间有所不同。你可以将其平均值并以常数c捕获。但是这里的基本操作—与每个人握手—总是与O(N)成正比，不pipe是什么。在辩论我们是否应该参加一个鸡尾酒会时，我们往往更感兴趣的是我们必须见面，而不是在这些会议的细节上。

O（N ^ 2）

鸡尾酒会的主持人希望你玩一个愚蠢的游戏，每个人都会遇到其他人。因此，你必须遇到N-1其他人，因为下一个人已经见过你，他们必须见到N-2个人，等等。这个系列的总和是x^2/2+x/2 。随着参会人数的增加， x^2项变得很快，所以我们就放弃了其他的一切。

O（N ^ 3）

你必须和别人见面，在每次会议中，你必须谈谈房间里的其他人。

O（1）

主持人想要宣布一些东西。他们喝了一个酒杯，大声说话。每个人都听到他们。事实certificate，有多less与会者并不重要，这个操作总是花费相同的时间。

O（log N）

主持人把所有人都按字母顺序排在桌旁。丹在哪里？你认为他必须在Adam和Mandy之间（当然不在Mandy和Zach之间！）。既然如此，乔治和曼迪之间呢？不，他必须在亚当和弗雷德之间，以及辛迪和弗雷德之间。等等…我们可以通过查看一半集合然后一半集合来有效地定位丹。最终，我们看O（log_2 N）个人。

O（N log N）

您可以使用上面的algorithmfind坐在桌子上的位置。如果有大量的人来到这个桌子上，一次一个，所有这一切都会花费O（N log N）时间。事实certificate，在必须比较任何一批物品时，需要多长时间进行分类。

最好的/最坏的情况

你到达派对，需要找Inigo – 需要多长时间？这取决于你什么时候到达。如果每个人都在四处磨砺，你会遇到最糟糕的情况：这将花费O(N)时间。但是，如果每个人都坐在桌旁，只需要O(log N)时间。或者，也许你可以利用主持人的酒杯 – 大声的力量，只需要O(1)次。

假设主机不可用，我们可以说Inigo发现algorithm具有O(log N)的下界和O(log N)的上界，这取决于你到达时的状态。

空间与沟通

同样的想法可以用来理解algorithm如何使用空间或通信。

Knuth写了一篇关于前者题为“歌曲的复杂性”的好文章。

定理2：存在复杂度为O（1）的任意长的歌曲。

certificate:(由于凯西和阳光乐队）。考虑由（15）定义的歌曲Sk，但是

 V_k = 'That's the way,' U 'I like it, ' U U = 'uh huh,' 'uh huh'

所有的k。

当你分析代码的时候，你必须逐行分析，计算每一个操作/识别时间复杂度，最后你必须总结一下才能得到整个图像。

例如，可以有一个线性复杂的简单循环，但后来在同一个程序中，可以有一个三元复杂的三重循环，所以程序将具有三次复杂性 。增长的function顺序就在这里发挥作用。

让我们来看看algorithm的时间复杂度的可能性，你可以看到上面提到的增长顺序：

常数有一个增长的顺序1 ，例如： a = b + c 。
对数时间有一个LogN增长的顺序，它通常发生在当你把东西分成两半时（二元search，树，甚至循环），或者以相同的方式相乘。

例如，线性 ，增长的顺序是N

 int p = 0; for (int i = 1; i < N; i++) p = p + 2;

Linearithmic ，增长的顺序是n*logN ，通常发生在分而治之algorithm。

立方体 ， N^3增长的顺序，经典的例子是你检查所有三元组的三重循环：

 int x = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) x = x + 2

指数，增长的顺序2^N ，通常发生在你进行穷举search时，例如检查一些集合的子集。

1.时间复杂度

维基百科将时间复杂度定义为

在计算机科学中，algorithm的时间复杂度量化algorithm作为代表input的string长度的函数运行的时间量。

2.为什么我们要谈论它？ 为什么如此重要？

时间复杂度有助于我们理解特定algorithm在input变大时的performance。如果让我们说你的algorithm需要1秒运行1K的input大小，当input大小加倍时，它将如何performance。它会在同一时间运行，加倍时间，四倍慢？在现实世界的编程中，预测input变大时algorithm的行为是非常重要的。

algorithm的时间复杂度通常用大O表示法表示。

下一个问题是什么？

3.什么是大O符号？

在Compter Science中，Big O用来描述algorithm的性能和复杂性。它具体描述了algorithm所需的最坏情况和执行时间。

要更深入地阅读这些关于SO的问题 – “大O”符号的简单英文解释是什么？和八岁的大O？

现在我们已经准备好了一些基础知识，让我们开始谈论示例代码的一些时间复杂性 –

4. O（1） – 恒定时间

一个algorithm的时间复杂度可以是O（1），只有当你的algorithm需要一个有限的时间量，不pipeinput是什么或者大小如何。例如，您的algorithm需要20毫秒，5纳秒或3秒，或者甚至15分钟，只要您的algorithm花费有限的时间，其时间复杂度为O（n）。

这是这样的代码的一个例子。

 public void GetFirstElement(int[] input) { return input[0]; }

访问数组索引（int a = ARR [5];）
在链接列表中插入一个节点
推堆栈上popup
插入和删除队列
查找Array中存储的树中父节点或左/右节点的子节点
跳转到双链表中的下一个/上一个元素

都是时间复杂度O（1）的例子。

5. O（n） – 线性时间

O（n） – 描述了一个algorithm，其性能与input的大小成正比例地线性增长。

 public void IsPresent(int[] input, int search) { for(int i = 0; i < input.length; i++) { if(input[i] == search) return true; } return false; }

上面的代码也演示了Big O如何支持最糟糕的性能情况。

这里是一些O（n）的例子 –

遍历一个数组
遍历链表
线性search
删除链接列表中的特定元素（不sorting）
比较两个string
检查回文
计数/桶sorting

6. O（n ² ）

所有algorithm的性能与input大小的平方成正比，其时间复杂度为O（n ² ）。

 public bool ContainsDuplicates(IList<string> elements) { for (var outer = 0; outer < elements.Count; outer++) { for (var inner = 0; inner < elements.Count; inner++) { // Don't compare with self if (outer == inner) continue; if (elements[outer] == elements[inner]) return true; } } return false; }

泡沫sorting
插入sorting
selectsorting
遍历一个简单的二维数组

在这个类别下是很less的例子。

O（n）是用来写algorithm时间复杂度的大O表示法。当你将一个algorithm中的执行次数加起来时，你会得到一个结果如2N + 2的expression式，在这个expression式中N是主导项（如果它的值增加或者减less，那么对expression式的影响最大）。现在O（N）是时间复杂性，而N是主导词。例

 For i= 1 to n; j= 0; while(j<=n); j=j+1;

这里内循环的总执行次数是n + 1，外循环的总执行次数是n（n + 1）/ 2，所以整个algorithm的总执行次数是n + 1 + n（n + 1/2 ）=（n ^ 2 + 3n）/ 2。这里n ^ 2是主导项，所以这个algorithm的时间复杂度是O（n ^ 2）

我知道这个问题已经回到原点，这里有一些很好的答案，但是我想分享一下在这篇文章中会遇到的math思维的人。大师定理在研究复杂性时是另一个有用的东西。我没有看到在其他答案中提到的。

为了得到一个algorithm的感觉，我经常做这个实验。简单地改变inputN，看看计算需要多长时间。这需要一些想法，因为big-O描述algorithm的最坏情况时间复杂度，并且发现最坏情况可能是棘手的。

从理论上讲，你的方法对我来说似乎是正确的：浏览程序（总是select最复杂的时间path），添加个人时间，摆脱所有的常量/因素。嵌套循环，跳跃等可以使这相当复杂，但我想不出一个silverlight的子弹来解决这个问题。

尽pipe它是相当math的，你也可能会在http://en.wikipedia.org/wiki/Big_O_notation中join 。

我也刚刚findhttp://en.wikipedia.org/wiki/Analysis_of_algorithms