big-o - 如果我在 for 循环中的终止语句是 i < n * n ，那么我的运行时间是 O(n^2) 吗？

Question

所以我对如何正确解释这个for循环的运行时间有点困惑： for (int i = 0; i < n * n; ++i) {}

我知道 O-Notation 的基础知识，我只是不知道如何正确解释运行时间，而且我找不到类似的例子。

问题实际上是一个三重嵌套 for 循环，我知道你只是将嵌套循环的运行时间相乘，但这让我不安全。

标签： big-o

Answer 1

是的。

n乘以自身是n ²，并且您执行n ²次迭代。

在这个简短的示例中，没有常数因素，也没有其他考虑因素。

复杂度只是O(n ² )。

请注意，这不考虑在循环内执行的任何假设操作。还要注意，如果我们完全按照表面价值来看待循环，它实际上并没有做任何有意义的工作，所以我们可以说它根本没有算法复杂性。您需要提供一个真实的例子才能真正说出来。