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

亚瑟·谢赫(Yasser Shaikh)

问题

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

在发布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!) ......和许多其他

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

安德鲁·托马佐斯(Andrew Tomazos)

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

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

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

我们为什么要删除两个2

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

考虑两个项2N和2。

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

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

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

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

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

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

因此2N成为正义N

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章