time-complexity - 单循环的最佳时间复杂度？

Question

我有一个非常简单的问题，我有这个循环：

for (int i=0; i<n; i++) {
    "some O(n) stuff here)"
}

该算法的最佳时间复杂度是多少？ 上）？ （对于循环O(1) * O(n)的东西） 还是 O(n^2)？ （for 循环O(n) * O(n)循环内的东西） for 循环本身是否会像往常一样被视为 O(n)，还是会被视为 O(1)，因为它只会进行 1 个循环对于最好的情况？

标签： time-complexitycomputer-science

Answer 1

你是对的，如果“stuff”的最佳运行时间是恒定的（甚至为零），那么最好的时间复杂度是 O(N)（甚至是 Θ(N)）。

无论如何，如果已知“stuff”是最好的情况 Ω(f(N))，那么最好的总时间是 Ω(N f(N))。