问题
如何找到算法的时间复杂度?
在发布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而不是声明的。
i=0
我 <N; 这将执行 N + 1 次
我++; 这将执行 N 次
因此,此循环所需的操作数为
{1+(N + 1)+ N} = 2N + 2
注意:这仍然可能是错误的,因为我对自己对计算时间复杂度的理解并不自信
我想知道什么?
好的,我想我知道这些小的基本计算,但是在大多数情况下,我认为时间复杂度为
O(N),O(N2),O(log n)的,为O(n!) ......和许多其他,
谁能帮助我了解如何计算一种算法的时间复杂度?我确定有很多像我这样的新手想知道这一点。
如何找到算法的时间复杂度
您将根据输入大小来执行多少条机器指令,然后将表达式简化为最大(当N非常大时)项,并且可以包括任何简化的常数因子。
例如,让我们看看如何简化2N + 2机器指令以将其描述为just O(N)。
2N + 2
O(N)
我们为什么要删除两个2?
2
随着N变大,我们对算法的性能感兴趣。
考虑两个项2N和2。
当N变大时,这两个项的相对影响是什么?假设N是一百万。
那么第一项是200万,第二项只有2。
因此,对于大的N,我们除最大项外都舍弃了所有项。
因此,现在我们从2N + 2转到2N。
2N
传统上,我们只对 直到恒定因素的 性能感兴趣。
这意味着当N大时,我们并不真正在意性能差异是否存在恒定的倍数。最初,2N的单位定义不明确。因此,我们可以乘以或除以一个常数因子,以获得最简单的表达式。
因此2N成为正义N。
N