我已经浏览过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 < N;
这将被执行N+1次 -
i++
这将被执行N次
因此该循环所需的运算次数为{1+(N+1)+N} = 2N+2。 (但这仍然可能是错误的,因为我对自己的理解没有信心。)
好吧,我想我知道这些小的基本计算,但在大多数情况下,我看到的时间复杂度为O(N)、O(n^2)、O(log n)、O(n!)和many others .
最佳答案
How to find time complexity of an algorithm
将其将执行的机器指令数添加为输入大小的函数,然后将表达式简化为最大项(当 N 非常大时),并且可以包含任何简化常量因子。
例如,让我们看看如何简化 2N + 2
机器指令,将其描述为 O(N)
。
为什么我们要删除两个 2
?
我们对 N 变大时算法的性能感兴趣。
考虑两项 2N 和 2。
当 N 变大时,这两项的相对影响是多少?假设 N 是一百万。
那么第一项就是200万,第二项只有2。
出于这个原因,我们放弃了除大 N 的最大项之外的所有项。
所以,现在我们已经从 2N + 2
变为 2N
。
传统上,我们只对达到常数因素的性能感兴趣。
这意味着当 N 很大时,我们并不真正关心性能差异是否存在恒定倍数。无论如何,2N 的单位一开始就没有明确定义。因此我们可以乘以或除以一个常数因子来得到最简单的表达式。
因此,2N
就变成了 N
。
关于algorithm - 如何找到算法的时间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40952614/