Python中文网

一个关于 编程问题的解答网站.

有 Java 编程相关的问题?

你可以在下面搜索框中键入要查询的问题!

如何求算法的时间复杂度

1 年 Questions & Answers

问题

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

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

我已经通过了this、this和许多其他链接

但在哪里我都找不到一个关于如何计算时间复杂度的清晰而直接的解释

我知道什么

对于下面这样简单的代码：

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

inti=0这将只执行一次。 时间实际上计算为i=0，而不是声明

i<；N这将执行N+1次

i++这将执行N次

因此，该循环所需的操作数为

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

注意：这可能仍然是错误的，因为我对自己对计算时间复杂性的理解没有信心

我想知道什么

好的，这些小的基本计算我想我知道，但在大多数情况下，我认为时间复杂性

O（N），O（n2），O（对数N），O（N！）。。。。和许多other

有人能帮我理解一个算法的时间复杂度是如何计算的吗？我相信有很多像我这样的新手想知道这一点


共 (6) 个答案

  1. # 1 楼答案

    How to find time complexity of an algorithm

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

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

    为什么要删除这两个2

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

    考虑两个术语2n和2。

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

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

    出于这个原因，除了大N的最大项外，我们放弃了所有项

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

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

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

    所以2N变成了N

  2. # 2 楼答案

    从这里开始-Introduction to Time Complexity of an Algorithm

    一,。导言

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

    二,。大O符号

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

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

    再举几个例子：

    • 1=O（n）
    • n=O（n2）
    • 对数（n）=O（n）
    • 2 n+1=O（n）

    三,。O（1）恒定时间：

    如果一个算法无论输入大小都需要相同的时间量，则称其在恒定时间内运行

    示例：

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

    四,。O（n）线性时间

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

    考虑下面的例子，下面我在线性搜索一个元素，它具有O（n）的时间复杂度。p> 

    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:包含方法
    • 队列：包含方法

    五,。O（对数n）对数时间：

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

    示例：Binary Search

    回想一下“二十个问题”游戏——任务是在一段时间内猜测一个隐藏数字的值。每次你做猜测时，你都会被告知你的猜测是过高还是过低。二十个问题的游戏意味着一种策略，使用你的猜测数字将间隔大小减半。这是一个被称为二进制搜索的通用问题解决方法的例子

    六,。O（n2）二次时间

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

    示例：

    七,。一些有用的链接

  3. # 3 楼答案

    时间复杂性与实例

    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;

    通用运行时间

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

    1. O（1）-恒定时间 恒定时间意味着运行时间是恒定的，它不受输入大小的影响

    2. O（n）–线性时间 当一个算法接受n个输入大小时，它也将执行n个操作

    3. O（对数n）–对数时间 运行时间为O（logn）的算法略快于O（n）。通常，算法会将问题分成大小相同的子问题。示例：二进制搜索算法、二进制转换算法

    4. O（n对数n）–线性时间 这种运行时间通常出现在“分治算法”中，该算法将问题递归地划分为子问题，然后在n个时间内合并它们。示例：合并排序算法

    5. O（n2）–二次时间 看冒泡排序算法

    6. O（n3）–立方时间 它的原理与O（n2）相同

    7. O（2n）–指数时间 当输入变大时，速度非常慢，如果n=1000.000，T（n）将为21000.000。蛮力算法有这个运行时间

    8. O（n！）–阶乘时间 最慢的！！！示例：旅行推销员问题（TSP）

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

  4. # 4 楼答案

    虽然这个问题有一些很好的答案。我想在这里用几个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

  5. # 5 楼答案

    这是一篇优秀的文章： 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符号。还要注意，这是一个非常简单的解释。大O是最常见的，但它也比我展示的更复杂。还有其他符号，如大ω、小o和大θ。在算法分析课程之外，您可能不会遇到这些问题

  6. # 6 楼答案

    当你分析代码时，你必须逐行分析它，计算每一个操作/识别时间复杂度，最后，你必须把它加起来得到整个画面

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

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

    • 恒定时间具有增长顺序1，例如：a = b + c

    • 对数时间有一个增长顺序LogN，它通常发生 当你将某物一分为二（二进制搜索、树、甚至循环）或以同样的方式将某物相乘时

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

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

    • 线性算法，增长顺序为^{，通常出现在分治算法中

    • 立方，增长顺序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，通常在执行穷举搜索时发生，例如检查某个集合的子集