大 O 表示法：使用流程图了解时间复杂度

大 O 表示法：使用流程图了解时间复杂度

大O表示法是分析算法时间复杂度的重要工具。本文通过流程图和代码示例，直观地展示了不同时间复杂度的特点，帮助读者更好地理解这一概念。

O(log(n)) - 对数时间

我直观地理解时间复杂度的方法是查看迭代器（例如 i*2），并查看函数有多少个循环。

O(n) - 线性时间

线性时间和对数时间看起来很相似，但由于循环条件的不同，输出有所不同。 exampleLogarithmic(100) 将返回 1, 2, 4, 8, 16, 32, 64，而 exampleLinear(100) 只是循环遍历 100 以下的所有正整数。

O(n^2) - 二次时间

循环次数与 n 的指数一致。您可以从字面上看到随着时间复杂度的增加，函数变得越来越大。

O(n^3) - 立方时间

这不是理解时间复杂度的唯一方法，但从字面上看到函数随着时间复杂度的增加而变长确实很有帮助。有时，用黑白块编写的代码无法让视觉学习者明白要点。

现在我们来做一个测验。这个函数的时间复杂度是多少？

猜猜看...

是线性的！我可以这么说，因为有一个循环，并且迭代器不会导致循环跳过任何整数。

这个函数的时间复杂度是多少？

不要怀疑自己。虽然这与第一个示例有点不同，但它具有线性时间复杂度。

这个函数的时间复杂度是多少？

您可能会在这里看到一种模式。这是线性的！

现在，如果您一直遵循我的逻辑，这可能是一个棘手的问题：

我说过指数n表示的循环数被提升到。为什么它的时间复杂度是线性的而不是二次的呢？

如果它在另一个 for 循环中显示一个 for 循环，那么时间复杂度将是二次方。然而，一个 for 循环在另一个 for 循环之后运行的时间复杂度不是二次的，而是线性的。

好的，那么这个函数的时间复杂度是多少？

这里没有什么棘手的。这具有二次时间复杂度。

现在，对于你的最后一个问题 - 一个质疑所有其他问题的问题 - 这个函数的时间复杂度是多少？

我希望您正在查看 for 循环的条件以及循环的绝对数量。由于循环条件 i<n，因此这是一个线性时间复杂度的函数。