algorithm - How to find time complexity of an algorithm?

Question

I have gone through Google and Stack Overflow search, but nowhere I was able to find a clear and straightforward explanation for how to calculate time complexity

What do I know already?

Say for a code as simple as the one below:

char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time

Say for a loop like the one below:

for (int i = 0; i < N; i++) {
    Console.Write('Hello World !');
}

int i=0; This will be executed only once. The time is actually calculated to i=0 and not the declaration.
i < N; This will be executed N+1 times
i++ This will be executed N times

So the number of operations required by this loop are {1+(N+1)+N} = 2N+2. (But this still may be wrong, as I am not confident about my understanding.)

OK, so these small basic calculations I think I know, but in most cases I have seen the time complexity as O(N), O(n^2), O(log n), O(n!), and many others.

score 449 · Accepted Answer

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

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

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

为什么我们要删除这两个2s ？

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

考虑两个术语 2N 和 2。

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

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

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

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

传统上，我们只对常数因子的性能感兴趣。

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

所以2N就变成了N。

score 434 · Accepted Answer

这是一篇很棒的文章： http ://www.daniweb.com/software-development/computer-science/threads/13488/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。您可能不会在算法分析课程之外遇到它们。;)

score 198 · Accepted Answer

取自这里 -算法的时间复杂度简介

一、简介

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

2.大O符号

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

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

还有几个例子：

1 = O(n)
n = O(n ² )
日志（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) 对数时间：

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

示例：二分搜索

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

6. O(n ² ) 二次时间

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

例子：

7.一些有用的链接

score 115 · Accepted Answer

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

O(n) ：如果循环变量以恒定量递增/递减，则循环的时间复杂度被视为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
}

例如选择排序和插入排序具有O(n^2)时间复杂度。

如果循环变量除以/乘以一个常数，则循环的O(Logn)时间复杂度被认为是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
}
```
例如，二分搜索具有O(Logn)时间复杂度。

O(LogLogn)循环的时间复杂度被认为是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.

所以上述算法的总时间复杂度(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

score 77 · Accepted Answer

时间复杂度与示例

1 - 基本操作（算术、比较、访问数组元素、赋值）：运行时间始终为常数 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)。

4 - 嵌套循环（循环内循环）：由于主循环内至少有一个循环，因此该语句的运行时间使用 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(n ² ) – 二次时间看冒泡排序算法！
O(n ³ ) – 立方时间它与 O(n ² ) 的原理相同。
O(2 ⁿ ) – 指数时间随着输入变大它非常慢，如果 n = 1000.000，T(n) 将是 21000.000。蛮力算法有这个运行时间。
O(n!) – 阶乘时间最慢！！！示例：旅行推销员问题 (TSP)

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

score 41 · Accepted Answer

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

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

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

常数时间有一个增长的顺序1，例如：a = b + c。
对数时间有一个增长顺序LogN，它通常发生在你将某物一分为二（二分搜索、树、甚至循环）或以相同方式相乘时。

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

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

线性的，增长的顺序是n*logN，通常出现在分而治之的算法中。

Cubic， order of growthN^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

Exponential， order of growth2^N，通常发生在您进行详尽搜索时，例如检查某些集合的子集。

score 40 · Accepted Answer

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

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

上）

当你到达派对时，你必须和每个人握手（对每个项目进行操作）。随着参加者人数的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 写了一篇关于前者的好论文，题为“歌曲的复杂性”。

定理 2：存在任意长的复杂度 O(1) 的歌曲。

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

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

对于所有 k。

score 5 · Accepted Answer

我知道这个问题可以追溯到很久以前，这里有一些很好的答案，但我想再分享一点给那些在这篇文章中会遇到数学问题的人。在研究复杂性时，Master theorem是另一个有用的知识。我没有在其他答案中看到它。

score 2 · Accepted Answer

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)