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

Question

我已经浏览了Google和Stack Overflow搜索，但是我没有找到一个关于如何计算时间复杂度的清晰而直接的解释

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

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

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

所以这个循环需要的操作数是{1（n1）N}=2n2。（但这可能仍然是错误的，因为我对自己的理解没有信心。）

好的，我想我知道这些小的基本计算，但是在大多数情况下，我已经看到时间复杂度为O（N），O（n^2），O（log n），O（n！）和许多其他的。




Answer 1

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

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

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

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

再举几个例子：

• 1=O（n）
• n=O（n²）
• 对数（n）=O（n）
• 2n1=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:包含方法
• 队列：包含方法

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

示例：二进制搜索

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

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

示例：

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

• 大O错误观念

Answer 2

这是一篇优秀的文章：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(

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

Answer 3

如何求算法的时间复杂度

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

例如，让我们看看我们如何简化2N 2机器指令，将其描述为O（N）。

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

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

考虑这两个术语2n和2。

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

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

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

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

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

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

所以2N变成了N。