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

Question

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

问题

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

在SO上发布问题之前我做了什么？

我走过了这个，这和许多其他链接

但是，我无法找到关于如何计算时间复杂度的明确而直接的解释。

我知道什么 ？

假设代码如下所示：

char h = 'y'; // This will be executed 1 timeint abc = 0; // This will be executed 1 time

说一个像下面这样的循环：

for (int i = 0; i < N; i++) {        
    Console.Write('Hello World !');}

int i = 0; 这只会执行一次。时间实际上是计算i=0而不是声明。

我<N; 这将执行N + 1次

i ++; 这将被执行N次

所以这个循环所需的操作数量是

{1+（N + 1）+ N} = 2N + 2

注意：这仍然可能是错误的，因为我对计算时间复杂度的理解没有信心

我想知道什么？

好吧，所以这些小基本计算我想我知道，但在大多数情况下，我已经看到了时间复杂度

O（N），O（N2），O（log n）的，为O（n！） ......和许多其他，

任何人都可以帮我理解如何计算算法的时间复杂度？我相信有很多像我这样的新手想知道这件事。

Answer 1

如何找到算法的时间复杂度您可以根据输入的大小计算它将执行多少个机器指令，然后将表达式简化为最大（当N非常大）时，可以包含任何简化常量因子。例如，让我们看看我们如何简化2N + 2机器指令来描述它O(N)。我们为什么要删除这两个2？当N变大时，我们对算法的性能感兴趣。考虑两个术语2N和2。当N变大时，这两个术语的相对影响是什么？假设N是一百万。然后第一个词是200万，第二个词只有2。出于这个原因，我们放弃了大N的最大条件。所以，现在我们已经离开2N + 2了2N。传统上，我们只对恒定因素的表现感兴趣。这意味着当N很大时，我们并不在乎是否存在性能差异的恒定倍数。无论如何，2N的单位首先没有明确定义。因此，我们可以乘以或除以常数因子来得到最简单的表达式。所以2N变得公正N。