如何计算算法的时间复杂度？

如何找到算法的时间复杂度

您将它将执行多少条机器指令作为其输入大小的函数相加，然后将表达式简化为最大（当N非常大时）项，并且可以包括任何简化的常数因子。

例如，让我们看看我们如何简化2N + 2机器指令以将其描述为O(N)。

为什么要删除两个2？

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

考虑两个术语2N和2。

当N变大时，这两个项的相对影响是什么？假设N是一百万。

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

出于这个原因，我们删除了除最大项以外的所有项。

所以，现在我们已经从2N + 2到2N。

传统上，我们只对性能到恒定因子感兴趣。

这意味着当N较大时，我们并不真正关心是否存在一些常数倍数的性能差异。无论如何，2N的单位一开始就没有明确定义。所以我们可以乘以或除以一个常数因子来得到最简单的表达式。

所以2N变成了N。

这是一篇精彩的文章：算法的时间复杂度

下面的答案是从上面复制的（以防优秀链接破产）

计算时间复杂度的最常见度量是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个对数循环（迭代或递归）组成，因此该算法是线性和对数的组合。

一般来说，用一维中的每个项目做某事是线性的，用二维中的每个项目做某事是二次的，将工作区域分成两半是对数的。还有其他的大O度量，如立方、指数和平方根，但它们并不那么常见。大O表示法被描述为O ( <type> )，其中<type>是度量。快速排序算法将被描述为O (N * log(N ))。

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

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₂+3n）/2。这里n^2是主导项，因此该算法的时间复杂度为O（n₂）。

从这里开始-算法的时间复杂度介绍

1.导言

在计算机科学中，算法的时间复杂度量化了算法运行所需的时间，作为表示输入的字符串长度的函数。

2.大O符号

算法的时间复杂度通常用大O表示法表示，它不包括系数和低阶项。当以这种方式表示时，时间复杂度被称为渐近描述，即随着输入大小变得无穷大。

例如，如果算法在所有大小为n的输入上所需的时间最多为5n³+3n，则渐近时间复杂度为O（n³）。稍后会详细介绍。

再举几个例子：

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

3. O（1）常数时间：

无论输入大小如何，如果算法需要相同的时间量，则称为恒定时间运行。

示例：

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

4. O（n）线性时间

如果算法的时间执行与输入大小成正比，则称为线性时间运行，即时间随着输入大小的增加而线性增长。

考虑下面的例子。下面我线性搜索一个元素，它的时间复杂度为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;}}

更多例子：

• 数组：线性搜索、遍历、查找最小值等
• ArrayList：包含方法
• 队列：包含方法

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

如果算法的时间执行与输入大小的对数成正比，则称其在对数时间内运行。

示例：二进制搜索

回想一下“二十个问题”游戏-任务是猜测间隔中隐藏数字的值。每次你猜测时，都会被告知你的猜测是太高还是太低。二十个问题游戏暗示了一种策略，使用你的猜测数字将间隔大小减半。这是称为二分搜索的通用问题解决方法的一个例子。

6. O（n²）二次时间

如果算法的时间执行与输入大小的平方成正比，则称其在二次时间内运行。

示例：

• 冒泡排序
• 选择排序选择排序
• 插入排序

7.一些有用的链接

• Big-O误解
• 确定算法的复杂性
• 大O备忘单

时间复杂度与示例

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) = 2if age < 17 then begin                      // 1status = "Not allowed!";              // 1end else beginstatus = "Welcome! Please come in";   // 1visitors = visitors + 1;              // 1+1 = 2end;

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

3-循环（进行、而、重复）：此语句的运行时间是循环数乘以该循环内的操作数。

示例：

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

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

4-嵌套循环（循环内循环）：由于主循环内至少有一个循环，因此该语句的运行时间使用O（n^2）或O（n^3）。

示例：

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

共同运行时间

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

1. O（1）-恒定时间

   恒定时间意味着运行时间是恒定的，它是不受输入大小的影响。

2. O（n）-线性时间

   当一个算法接受n个输入大小时，它也会执行n个操作。

3. O（log n）-对数时间

   运行时间为O（log n）的算法比O（n）稍快。通常，算法将问题分成大小相同的子问题。示例：二进制搜索算法、二进制转换算法。

4. O（n log n）-线性线粒体次

   这种运行时间通常存在于“分治算法”中，它将问题递归地划分为子问题，然后在n次内合并它们。示例：合并排序算法。

5. O（n²）-二次时间

   看泡泡排序算法！

6. O（n³）-立方时间

   它与O（n²）具有相同的原理。

7. O（2ⁿ）-指数时间

   当输入变大时，它非常慢，如果n=1,000,000，T（n）将是21,000,000。蛮力算法有这个运行时间。

8. O（n！）-阶乘时间

   示例：旅行推销员问题（TSP）

它取自这篇文章。它解释得很好，你应该读一读。

松散地说，时间复杂度是一种总结算法的操作数量或运行时间如何随着输入大小的增加而增长的方法。

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

O（N）

到达聚会现场时，你需要和所有人握手（每件物品都要做一次操作），随着出席人数N的增加，和所有人握手所需的时间/工作量随着O(N)的增加而增加。

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

与人握手所需的时间是有差异的。你可以把它平均下来，并用一个常数c来捕捉它。但是这里的基本操作——与每个人握手——总是与O(N)成正比，不管c是什么。在讨论我们是否应该去参加鸡尾酒会时，我们通常更感兴趣的是我们必须会见每个人这一事实，而不是这些会议是什么样子的微小细节。

O（N^2）

鸡尾酒会的主持人想让你玩一个愚蠢的游戏，每个人都认识其他人。因此，你必须认识N-1其他人，因为下一个人已经认识你了，他们必须认识N-2人，依此类推。这个系列的总和是x^2/2+x/2。随着与会者人数的增长，x^2项变得更大快速，所以我们就放弃了其他一切。

O（N^3）

你必须与其他人见面，在每次会议期间，你必须谈论房间里的其他人。

O（1）

主持人要宣布一件事。他们点着酒杯，大声说话。每个人都听到了。事实证明，不管有多少人参加，这个操作总是花费同样的时间。

O（log N）

主持人已经按字母顺序把每个人都安排到了餐桌上。丹在哪里？你的理由是他一定在亚当和曼迪之间（当然不是曼迪和扎克之间！）。有鉴于此，他在乔治和曼迪之间吗？不。他一定在亚当和弗雷德之间，辛迪和弗雷德之间。以此类推……我们可以通过看一半的人，然后看一半的人来有效地找到丹。最终，我们看的是0个人。

O（N log N）

你可以使用上面的算法找到在桌子旁坐下的位置。如果一次有很多人来到桌子旁，并且所有人都这样做，那将花费O（N log N）时间。这实际上是在必须进行比较时对任何项目集合进行排序所需的时间。

最佳/最差案例

你到达派对并需要找到Inigo-需要多长时间？这取决于你何时到达。如果每个人都在你身边，那么最坏的情况是：需要O(N)时间。然而，如果每个人都坐在桌旁，只需要O(log N)时间。或者你可以利用主人的酒杯呼喊能力，只需要O(1)时间。

假设主机不可用，我们可以说Inigo查找算法的下界为O(log N)，上限为O(N)，具体取决于您到达时的聚会状态。

空间与通信

同样的想法可以应用于理解算法如何使用空间或通信。

高德纳写了一篇关于前者的好论文，题为《歌曲的复杂性》。

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

证明：（由于Casey和阳光乐队）。考虑由（15）定义的歌曲Sk，但是

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

对于所有k

循环的几个例子。

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

    // Here c is a positive integer constantfor (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²）

    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}

  例如，选择排序和插入排序的时间复杂度为O（n²）。

• 如果循环变量除以/乘以常量，则循环的O（log n）时间复杂度被认为是O（log n）。

    for (int i = 1; i <=n; i *= c) {// some O(1) expressions}for (int i = n; i > 0; i /= c) {// some O(1) expressions}
  For example, [binary search][3] has _O(log&nbsp;n)_ time complexity.

• O（log log n）循环的时间复杂度被认为是O（log log n），如果循环变量按常数指数减少/增加。

    // Here c is a constant greater than 1for (int i = 2; i <=n; i = pow(i, c)) {// some O(1) expressions}//Here fun is sqrt or cuberoot or any other constant rootfor (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.

因此，上述算法的总时间复杂度为(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（log n）。所以上面代码的时间复杂度是O（n·log n）。

参考文献：

123

对于有数学头脑的人来说：在研究复杂性时，主定理是另一个有用的东西。

当你分析代码时，你必须逐行分析它，计算每个操作/识别时间复杂度。最后，你必须总和才能获得全貌。

例如，您可以有一个带有线性复杂度的简单循环，但稍后在同一程序中，您可以有一个带有三次复杂度的三重循环，因此您的程序将具有三次复杂度。函数的增长顺序在这里发挥作用。

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

• 恒定时间的增长顺序为1，例如：a=b+c。

• 对数时间的增长顺序为log n。它通常发生在你将某物分成两半（二分查找，树，甚至循环）或以相同的方式乘以某物时。

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

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

• 线性的。增长的顺序是n·log n。它通常发生在分而治之算法。

• <强>立方。增长的顺序是N³。一个经典的例子是一个三重循环，您可以在其中检查所有三元组：

   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。它通常发生在您进行穷举搜索时，例如，检查某些集合的子集。

其他答案集中在大O符号和实际示例上。我想通过强调理论观点来回答这个问题。下面的解释必然缺乏细节；学习计算复杂性理论的一个很好的来源是Michael Sipser的计算理论导论。

图灵机

研究任何计算问题最普遍的模型是图灵机。图灵机有一个由符号组成的一维磁带，用作存储设备。它有一个磁带头，用于从磁带上写入和读取。它有一个确定机器行为的过渡表，这是一个固定的硬件组件，在机器创建时决定。图灵机以离散的时间步工作，执行以下操作：

它读取磁带头下的符号。根据符号及其内部状态（只能取有限多个值），它从其转换表中读取三个值s，σ和X，其中s是内部状态，σ是符号，X是右或左。

它将其内部状态更改为s。

它将读取的符号更改为σ。

它根据X中的方向移动磁带头一步。

图灵机是强大的计算模型。它们可以做你的数字计算机能做的一切。它们是在数字现代计算机出现之前由理论计算机科学和数学家之父阿兰·图灵介绍的。

时间复杂度

很难定义单个问题的时间复杂度，比如“白棋在国际象棋中有获胜的策略吗？”因为有一台机器只跑了一步就给出了正确的答案：机器直接说“不”或直接说“是”。为了使它工作，我们定义了一系列问题的时间复杂度L，每个问题都有一个大小，通常是问题描述的长度。然后我们用一台图灵机M正确地解决了该系列中的每个问题。当M被赋予这个大小为n的家庭的问题时，它会通过有限多个步骤解决它。让我们称f（n）为M解决大小为n的问题所需的最长时间。然后我们说L的时间复杂度是O（f（n）），这意味着有一个图灵机最多在M0时间内解决大小为n的实例，其中M1是独立于n的常数。

它不是依赖于机器吗？数字计算机能做得更快吗？

是的！有些问题可以通过其他计算模型更快地解决，例如两盘磁带图灵机解决一些问题比一盘磁带更快。这就是为什么理论家更喜欢使用鲁棒的复杂性类，如NL、P、NP、PSPACE、EXPTIME等。例如，P是决策问题的类，其时间复杂度为O（p（n）），其中p是多项式。即使你向图灵机添加一万盘磁带，或使用其他类型的理论模型，如随机存取机，P类也不会改变。

理论与实践的差异

通常假设整数加法的时间复杂度为O（1）。这个假设在实践中是有道理的，因为计算机在许多应用中使用固定数量的位来存储数字。理论上没有理由假设这样的事情，所以加法的时间复杂度是O（k），其中k是表达整数所需的位数。

发现一类问题的时间复杂度

显示问题时间复杂度的直接方法是O（f（n））构建一个图灵机，在O（f（n））时间内解决它。为复杂问题创建图灵机并非易事；人们需要对它们有所熟悉。图灵机的转换表很少给出，而且是高级描述。随着人们对机器的熟悉，更容易看到机器需要多长时间才能停止。

显示一个问题是没有O（f（n））时间复杂度是另一回事……即使有一些像时间层次定理这样的结果，这里也有许多悬而未决的问题。例如，NP中的问题是否在P中，即在多项式时间内可解，是数学中七个千年奖问题之一，其解决者将获得100万美元。