JavaScript 算法基础第 2 部分：探索一种更好的机制来推导算法的时间复杂度。

本文是上一篇文章的续篇，我们研究了算法和时间复杂度的基础知识。

我们还看到了如何通过识别具有不同输入的函数的时间模式来评估算法的时间复杂度。 但是，如前文所述，这种基于时间模式评估时间复杂度的方法并不可靠，因为它还取决于其他因素。

因此，我们需要一种更好的机制来推导出独立于任何其他因素的算法的时间复杂度。 我们将在本文中研究这种机制。

但是，在直接开始之前，让我们先了解一下大 O 表示法。

大 O 符号

除了线性时间和常数时间之外，我们还发现了具有对数时间、二次时间甚至三次时间的算法。 还有很多其他时间复杂性。 但这些是一些常见的。

在我们之前的文章中，我们能够得出结论，具有循环解的函数具有线性时间复杂度，而具有数学解的函数具有恒定时间复杂度。 但是，如果我们必须以标准方式表示或传达它，那我们怎么能做到呢？

在编程中，我们用一种叫做 Big O Notation 的东西来表示它。 这只是让我们更容易表达给定算法的时间复杂度。 Big O Notation 看起来像这样，按照性能从好到差的顺序排列。

Big O Notation 是比较和表示算法性能的标准方法。我们推导出算法的大 O，然后我们知道 O(n) 是线性的，O(1) 是常数。这里的 (O) 表示函数的顺序。此外，我们使用这个符号来表达任何算法的复杂性。

现在，既然我们对大 O 表示法很清楚，让我们看看推导算法大 O 的实际方法。

导出时间复杂度/大 O（渐近分析）

在上一篇文章中，我们了解到我们应该关心函数模式而不是具体的时间数。因此，对于循环函数，我们可以说它的时间复杂度为 O(n)，这意味着它具有线性时间复杂度。

但是，这是通过比较函数的时间值来完成的，我们已经知道这不是一个可靠的解决方案，因为它取决于其他因素。那么，我们如何得出这个呢？

为此，我们使用一种称为渐近分析的技术。

它涉及几个简单的步骤。首先，对于给定的算法，我们定义它的功能。现在，我的意思是我们编写的数学函数，以得到我们在线性函数中看到的图形。因此，我们需要推导出最终将导致如下线性图的数学函数。让我们看看如何推导出它。

这听起来可能很可怕，但并不难。 我们需要做的就是计算函数中表达式执行的次数。 粗略地说，函数中的每一行代码，我们计算它被执行的频率。

请注意，使用这种方法，我们无法获得以毫秒或秒为单位的真实时间。 理解这一点很重要，因为现在我们不再对时间感兴趣，因为它不可靠并且受太多方面的影响。

事实上，我们只是假设 JavaScript 中的每个表达式都花费大致相同的时间。 然后可以计算表达式执行的数量，然后可以将该数量简单地与另一个替代函数的数量进行比较。

这就是我们将在这里采取的方法。 让我们用我们的循环函数来看看几个场景。

我们已经将数组输入的长度定义为 n 因子。 我们将找到具有不同长度数组的函数的行为，即

n = [1]n = [1,2,3,4,5]n = [1,2,3,4,5,6,7,8,9,0]

在所有情况下，我们都会遍历函数中的每一行表达式，看看它被执行了多少次。

1. 第一个表达式，

let total = 0;

这在所有情况下都只执行一次，因为它只是一个赋值。

2.for循环初始化的下一个表达式，

for(let index = 0; index < n.length; index++)

由于这也是一个初始化，因此在所有三种情况下它只执行一次。

3.接下来，我们有for循环的主体，

total += n[index];

在这里你会看到结果不同，对于长度为 1 的数组，它只执行一次，但对于长度为 5 和 10 的数组，它分别执行 5 次和 10 次。 而且，这很重要。

4.然后我们有一个return语句，

return total;

在所有情况下也只执行一次。

如果我们在所有三种情况下都看到表达式的代码执行，那么我们在这里再次看到一个模式。 对于这个算法，我们可以说函数的唯一动态部分是循环中的 body(total += n[index];)。 这个主体被执行的次数就是我们输入这个函数的数组的长度。

因此，对于 n = n（数组的 n 长度），其他三个表达式将只运行一次，但循环中的代码 (total += n[index];) 将执行 n 次。 而且，有了这个，我们现在可以推导出一个函数。

如果我们想用 T 来表示这里的时间复杂度，那么我们可以说，对于 n = n 的情况，我们为这个函数得到的代码执行次数是 (1 + 1 + n + 1)，即

n=[1]                   -> T = 1 + 1 + 1 + 1n=[1,2,3,4,5]           -> T = 1 + 1 + 5 + 1n=[1,2,3,4,5,6,7,8,9,0] -> T = 1 + 1 + 10 + 1n=[n]                   -> T = 1 + 1 + n + 1

Therefore,

T = 1 + 1 + n + 1

We can sum this up to,

T = n + 3

This can also be written as,

T = 1*n + 3

This is the mathematical function equation that would describe the number of code executions we have for the above JavaScript function.

It does not describe the number of milliseconds or seconds this function takes, because that is hard to quantify anyways. But, if we assume that every line of code roughly takes the same amount of time to execute, then we can use such an equation to compare this algorithm to other algorithms.

Therefore, we can generalize that and also write the equation as,

T = a*n + b            (1 is replaced by 'a' & 3 is replaced by 'b')

现在，为了导出大 O 表示法，我们需要找到该函数中增长最快的项。 这很容易，它是，

a*n

因为 b 是一个不会增长的常数系数。 它总是完全相同的数字。 因此我们可以忽略它。 另一方面，a*n 实际上取决于 n，对于更大的 n，该项也更大。

由于我们找到了增长最快的项，即 a*n 从该项中删除系数 a，因为我们现在不关心确切的数字，我们关心的是总体情况。 这个过程在这里被称为渐近分析。

现在，我们可以将其缩小到下面的函数方程。

T = n

这清楚地告诉我们这个函数的时间复杂度取决于 n。 而且，这 n 只是我们放在 Big O 表示法的括号之间的内容，即

O(n)

所以，

T = O(n)

这就是为什么我们称它为 n 的大 O 并将其表示为线性函数的 T = O(n)。

类似地，我们可以使用上述渐近分析的方法来推导任何算法的大 O。 它不依赖于任何其他因素，并且与我们之前使用的时间函数方法相比更可靠。

感谢您的阅读。

关注七爪网，获取更多APP/小程序/网站源码资源！