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

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。