一尘不染

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

algorithm

问题

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

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

我经历了这个,这个和许多其他链接

但是我无法在哪里找到关于如何计算时间复杂度的清晰直接的解释。

我知道什么 ?

说一个简单的代码如下:

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而不是声明的。

我 <N; 这将执行 N + 1

我++; 这将执行 N

因此,此循环所需的操作数为

{1+(N + 1)+ N} = 2N + 2

注意:这仍然可能是错误的,因为我对自己对计算时间复杂度的理解并不自信

我想知道什么?

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

O(N),O(N2),O(log n)的,为O(n!)
......和许多其他

谁能帮助我了解如何计算一种算法的时间复杂度?我确定有很多像我这样的新手想知道这一点。


阅读 193

收藏
2020-07-28

共1个答案

一尘不染

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

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

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

我们为什么要删除两个2

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

考虑两个项2N和2。

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

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

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

因此,现在我们从2N + 2转到2N

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

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

因此2N成为正义N

2020-07-28