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

Question

我已经经历了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 .

Answer 1

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。