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

Question

我已经通过谷歌和堆栈溢出搜索，但我没有找到一个关于如何计算时间复杂度的清晰而直接的解释。

说代码像下面这样简单：

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（logn），O（N！），还有很多其他的。




Answer 1

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

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

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

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

再举几个例子：

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

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

示例：二进制搜索

回想一下“二十个问题”游戏——任务是猜测区间中隐藏数字的值。每次你猜测，你都会被告知你的猜测是太高还是太低。二十个问题游戏暗示了一种使用你的猜测数字将区间大小减半的策略。这是一个被称为二分搜索的一般问题解决方法的例子。

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

例子：

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

• Big-O误解
• 确定算法的复杂性
• Big O备忘单

Answer 2

这是一篇优秀的文章：算法的时间复杂性

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

计算时间复杂度的最常用指标是大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万，第二学期只有200万。

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

现在我们从2n2到2N。

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

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

所以2N变成了N。