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

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

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

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

为什么要删除这两个 2？

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

考虑两个术语 2N 和 2。

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

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

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

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

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

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

所以 2N 变成了 N。

---

这是一篇很棒的文章：Time complexity of algorithm

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

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

请注意，这些都没有考虑到最佳、平均和最坏情况的措施。每个都有自己的大 O 符号。另请注意，这是一个非常简单的解释。 Big O 是最常见的，但也比我展示的更复杂。还有其他符号，例如大 omega、小 o 和大 theta。您可能不会在算法分析课程之外遇到它们。 ;)

---

取自这里 - Introduction to Time Complexity of an Algorithm

一、简介

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

2.大O符号

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

例如，如果算法对大小为 n 的所有输入所需的时间最多为 5n3 + 3n，则渐近时间复杂度为 O(n3)。稍后再谈。

再举几个例子：

1 = O(n)

n = O(n2)

日志（n）= O（n）

2 n + 1 = O(n)

3. O(1) 恒定时间：

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

例子：

数组：访问任何元素

固定大小的堆栈：push 和 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) 对数时间：

如果算法的执行时间与输入大小的对数成比例，则称该算法以对数时间运行。

示例：Binary Search

回想一下“二十题”游戏——任务是在一个区间内猜测一个隐藏数字的值。每次您进行猜测时，系统都会告诉您您的猜测是太高还是太低。二十个问题游戏意味着使用您的猜测数将间隔大小减半的策略。这是称为二进制搜索的一般问题解决方法的示例。

6. O(n2) 二次时间

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

例子：

冒泡排序

选择排序

插入排序

7.一些有用的链接

大 O 的误解

确定算法的复杂性

大 O 备忘单

---

循环的几个例子。

如果循环变量以恒定量递增/递减，则循环的 O(n) 时间复杂度被视为 O(n)。例如以下函数具有 O(n) 时间复杂度。 // 这里 c 是一个正整数常量 for (int i = 1; i <= n; i += c) { // 一些 O(1) 表达式 } for (int i = n; i > 0; i -= c) { // 一些 O(1) 表达式 }

嵌套循环的 O(nc) 时间复杂度等于执行最里面的语句的次数。例如，以下示例循环的时间复杂度为 O(n2) for (int i = 1; i <=n; i += c) { for (int j = 1; j <=n; j += c) { // 一些 O(1) 表达式 } } for (int i = n; i > 0; i += c) { for (int j = i+1; j <=n; j += c) { // 一些O(1) 表达式 } 例如，选择排序和插入排序具有 O(n2) 时间复杂度。

如果循环变量除以/乘以一个常数，则循环的 O(log n) 时间复杂度被视为 O(log n)。 for (int i = 1; i <=n; i *= c) { // 一些 O(1) 表达式 } for (int i = n; i > 0; i /= c) { // 一些 O(1 ) 表达式 } 例如，[二分搜索][3] 的时间复杂度为 _O(log n)_。

如果循环变量以恒定的量以指数方式减少/增加，则循环的 O(log log n) 时间复杂度被视为 O(log log n)。 // 这里 c 是一个大于 1 的常数 for (int i = 2; i <=n; i = pow(i, c)) { // 一些 O(1) 表达式 } //这里 fun 是 sqrt 或 cuberoot 或(int i = n; i > 0; i = fun(i)) { // 一些 O(1) 表达式 }

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

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)。

参考：

1 2 3

---

时间复杂度与示例

- 基本操作（算术、比较、访问数组元素、赋值）：运行时间始终为常数 O(1)

例子：

read(x)                               // O(1)
a = 10;                               // O(1)
a = 1,000,000,000,000,000,000         // O(1)

2 - If then else 语句：仅从两个或多个可能的语句中获取最大运行时间。

例子：

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。因此，它的大 oh 仍然是常数 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)。

- 嵌套循环（循环内循环）：由于主循环内至少有一个循环，因此该语句的运行时间使用 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;

常用运行时间

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

O(1) – 常数时间常数时间意味着运行时间是常数，它不受输入大小的影响。 O(n) - 线性时间 当算法接受 n 个输入大小时，它也会执行 n 个操作。 O(log n) – 对数时间算法，运行时间为 O(log n)，略快于 O(n)。通常，算法将问题分成大小相同的子问题。示例：二分查找算法、二分转换算法。 O(n log n) – 线性时间这个运行时间经常出现在“分治算法”中，它递归地将问题划分为子问题，然后在 n 时间内将它们合并。示例：合并排序算法。 O(n2) - 二次时间看冒泡排序算法！ O(n3) – 三次时间 它与 O(n2) 的原理相同。 O(2n) – 指数时间随着输入变大它非常慢，如果 n = 1,000,000，T(n) 将是 21,000,000。蛮力算法有这个运行时间。 O(n!) – 阶乘时间最慢！！！示例：旅行商问题 (TSP)

它取自 this article。它解释得很好，你应该读一读。

---

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

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

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

常数时间的增长阶数为 1，例如：a = b + c。

对数时间的增长顺序为 log N。它通常发生在您将某物一分为二（二分搜索、树，甚至循环）或以相同方式相乘时。

线性的。增长的阶数为N，例如int p = 0； for (int i = 1; i < N; i++) p = p + 2;

线性的。增长的顺序是n·log N。它通常出现在分而治之的算法中。

立方体。增长的顺序是N3。一个经典的例子是一个三元组循环，你检查所有的三元组： 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

指数的。增长的顺序是2N。它通常发生在您进行详尽搜索时，例如，检查某个集合的子集。

---

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

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

上）

当你到达派对时，你必须和每个人握手（对每个项目进行操作）。随着参加者人数 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)

主持人按字母顺序将每个人都安排在了餐桌上。丹在哪里？你推断他一定介于亚当和曼迪之间（当然不是在曼迪和扎克之间！）。鉴于此，他在乔治和曼迪之间吗？不，他必须在亚当和弗雷德之间，在辛迪和弗雷德之间。依此类推……我们可以通过查看一半的集合然后查看该集合的一半来有效地定位 Dan。最终，我们看 O(log_2 N) 个个体。

O(N log N)

您可以使用上面的算法找到在桌子上坐下的位置。如果有大量的人来到餐桌旁，一次一个，并且所有人都这样做，那将花费 O(N log N) 时间。事实证明，当必须对任何项目集合进行比较时，对它们进行排序需要多长时间。

最好/最坏情况

你到了派对，需要找到 Inigo - 需要多长时间？这取决于你什么时候到达。如果每个人都围着你转，你就遇到了最坏的情况：这需要 O(N) 时间。但是，如果每个人都坐在桌旁，则只需 O(log N) 时间。或者，也许您可以利用主持人的酒杯喊叫能力，并且只需要 O(1) 时间。

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

空间与通讯

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

Knuth 写了一篇关于前者的好论文，题为 "The Complexity of Songs"。

定理 2：存在任意长的复杂度 O(1) 的歌曲。证明：（由于凯西和阳光乐队）。考虑由 (15) 定义的歌曲 Sk，但是

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

对于所有 k。

---

对于有数学头脑的人：master theorem 是研究复杂性时另一个有用的知识。

---

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

---