小编典典

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

all

说一个像下面这样简单的代码:

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! )等等.


阅读 141

收藏
2022-02-28

共1个答案

小编典典

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

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

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

为什么我们要删除这两个2s ?

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

考虑两个术语 2N 和 2。

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

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

出于这个原因,我们删除了除大 N 的最大项之外的所有项。

所以,现在我们已经从2N + 22N

传统上,我们只对常数因子的性能感兴趣。

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

所以2N就变成了N

2022-02-28