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

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 !');
}

答案

这是一篇很棒的文章: 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;
}

是对数的。该算法的运行时间与 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 个对数的循环(迭代或递归)组成,因此该算法是线性和对数的组合。

通常,对一维中的每个项目执行某项操作是线性的,对二维中每一个项目执行某项操作是二次项,将工作区域分为两半是对数的。还有其他 Big O 度量,例如立方,指数和平方根,但它们并不常见。大 O 表示法描述为 O(),这里是小数位。快速排序算法将描述为 O(N * log(N))。

请注意,所有这些都未考虑最佳,平均和最坏情况下的度量。每个都有自己的 Big O 表示法。另请注意,这是一个非常简单的解释。大 O 是最常见的,但我已经展示过它更加复杂。还有其他符号,例如大欧米茄,小 o 和大 theta。在算法分析课程之外,您可能不会遇到它们。 ;)

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

您将根据输入大小来执行多少条机器指令,然后将表达式简化为最大(当 N 非常大时)项,并且可以包括任何简化的常数因子。

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

为什么我们删除两个2 s?

随着 N 变大,我们对算法的性能感兴趣。

考虑两个项 2N 和 2。

随着 N 变大,这两个项的相对影响是什么?假设 N 是一百万。

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

因此,对于大的 N,我们除最大项外都舍弃了所有项。

因此,现在我们从2N + 2变为2N

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

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

所以2N变成N

摘自此处 - 算法时间复杂度简介

1. 简介

在计算机科学中,算法的时间复杂度根据代表输入的字符串的长度来量化算法运行所花费的时间。

2. 大 O 符号

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

例如,如果算法在大小为 n 的所有输入上所需的时间最多为 5n 3 + 3n,则渐近时间复杂度为 O(n 3 )。以后再说。

其他几个例子:

  • 1 = O(n)
  • n = O(n 2
  • log(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(n2)二次时间

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

例子:

7. 一些有用的链接

尽管对于这个问题有一些好的答案。我想在这里用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

时间复杂度示例

1 - 基本操作(算术,比较,访问数组的元素,分配):运行时间始终为常数 O(1)

范例:

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

2 - 如果则 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 - 循环(重复执行):此语句的运行时间是循环数乘以该循环内的操作数。

例:

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;

普通运行时间

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

  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 2 )–二次时间看气泡排序算法!

  6. O(n 3 )–立方时间它与 O(n 2 )具有相同的原理。

  7. O(2 n )–指数时间随着输入变大,这非常慢,如果 n = 1000.000,则 T(n)为 21000.000。蛮力算法具有此运行时间。

  8. O(n!)–阶乘时间最慢!示例:旅行推销员问题(TSP)

摘自本文 。很好的解释应该给读。

在分析代码时,必须逐行进行分析,计算每个操作 / 识别时间的复杂性,最后,必须对其求和以得到完整的图像。

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

让我们看一下算法时间复杂度的可能性,您可以看到上面提到的增长顺序:

  • 恒定时间的增长顺序为1 ,例如: a = b + c

  • 对数时间的增长顺序为LogN ,通常在将某物分成两半(二进制搜索,树,偶数循环)或以相同方式相乘时出现。

  • 例如,线性 ,增长顺序为N

    int p = 0;
    for (int i = 1; i < N; i++)
      p = p + 2;
  • 线性运算的增长顺序为n*logN ,通常发生在分治法中。

  • 三次 ,增长顺序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 ,通常在进行穷举搜索(例如检查某个集合的子集)时发生。

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

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

上)

参加聚会时,您必须与所有人握手(对每个项目进行操作)。随着与会者人数N增加,握手的时间 / 工作将随着O(N)增加而增加。

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

与人握手所需的时间有所不同。您可以将其取平均值并以常数c捕获。但是无论c是什么,这里的基本运算 - 与所有人握手 - 总是与O(N)成比例。在辩论我们是否应该参加鸡尾酒会时,我们通常对与所有人见面的事实比对这些会议的详细情况更感兴趣。

O(N ^ 2)

鸡尾酒会的主持人希望您玩一个愚蠢的游戏,让所有人见面。因此,您必须会见N-1其他人,并且因为下一个人已经见过您,所以他们必须会见N-2个人,依此类推。这个系列的总和是x^2/2+x/2 。随着与会者人数的增加, x^2项变得越来越 ,因此我们只剩下其他所有内容。

O(N ^ 3)

您必须与其他所有人见面,并且在每次会议期间,您都必须谈论会议室中的其他所有人。

O(1)

主持人想宣布一些事情。他们在酒杯上叮叮当当,大声说话。每个人都听到。事实证明,参加会议的人数无关紧要,该操作始终花费相同的时间。

O(对数 N)

主持人已按字母顺序将所有人安排在桌子旁。丹在哪里?您认为他一定在亚当和曼迪之间(一定不在曼迪和扎克之间!)。鉴于此,他在乔治和曼迪之间吗?不。他必须在亚当和弗雷德之间,以及辛迪和弗雷德之间。依此类推... 通过查看一半的集合,然后查看一半的集合,我们可以有效地定位 Dan。最终,我们看O(log_2 N)个人。

O(N 对数 N)

您可以使用上述算法在桌旁找到坐下的地方。如果有很多人一次来到桌子上,而所有人都这样做了,那将花费O(N log N)时间。事实证明,在必须对所有项目集合进行排序时,需要花费多长时间。

最佳 / 最坏情况

您到达聚会并需要找到 Inigo - 需要多长时间?这取决于您何时到达。如果每个人都四处乱逛,您会遇到最坏的情况:这将花费O(N)时间。但是,如果每个人都坐在桌旁,则只需要O(log N)时间。或者,也许您可以利用主持人的酒杯启动功能,而这只需要O(1)时间。

假设主机不可用,可以说 Inigo 查找算法的下限为O(log N) ,上限为O(N) ,具体取决于到达时一方的状态。

太空与通讯

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

克努斯(Knuth)撰写了一篇有关前者的好论文,题为“歌曲的复杂性”

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

证明:(由于 Casey 和阳光乐队)。考虑由(15)定义的 Sk 歌曲

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

对于所有 k。

我知道这个问题可以追溯到过去,这里有一些很好的答案,尽管如此,我还是想与那些精通数学的人分享一下,他们将在本文中绊倒。 掌握定理是研究复杂性时要知道的另一件事。我没有在其他答案中看到它。

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)