如何求出算法的时间复杂度？ [英] How to find time complexity of an algorithm?

问题描述

我已经进行了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(Logn)、O(n！)和许多others。

推荐答案

如何计算算法的时间复杂度

将它将执行的机器指令数加起来作为其输入大小的函数，然后将表达式简化为最大项(当N非常大时)，并且可以包括任何简化常量因子。

例如，让我们看看如何将2N + 2机器指令简化为O(N)。

为什么要删除这两个2%s？

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

考虑术语2N和2。

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

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

因此，我们删除除最大N之外的所有术语

所以，现在我们已经从2N + 2转到2N。

传统上，我们只对性能至恒定因子感兴趣。

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

因此2N变为仅N。

这篇关于如何求出算法的时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！