单循环的最佳时间复杂度?

Question

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

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

这个算法的最佳时间复杂度是多少?O (n) ?(for loopO(1)*O (n))或东西O (n ^ 2) ?(for loopO(n))*O (n)for循环本身将被视为O(n)，还是将被视为O(1)因为它只会在最好的情况下只做一个循环?

Answer 1

你是对的，最好的时间复杂度是O(N)(甚至Θ(N))，如果"东西"的最佳运行时间是;是常数(甚至为零)。

无论如何，如果"东西"已知最佳情况Ω(f(N))，则最佳总时间为Ω(N f(N))。

Answer 2

如果你的循环对n做O(n)的事情，那么时间复杂度将是O(n^2)。愿你称之为最坏的情况。最佳情况和平均情况将基于每次循环迭代时执行的some O(n) stuff。

让我们举一个简单的冒泡排序算法的例子:

for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (a[j] > a[j + 1]) {
swap(&a[j], &a[j + 1]);
}
}
}

时间复杂度无论数组是否排序(无论升序还是降序)，该值始终为O(n^2)。

但这可以通过观察n^th传递找到n^th最大的元素并将其放入最终位置来优化。因此，当运行n时间时，内循环可以避免查看最后的n − 1项:

for (int i = 0; i < n - 1; ++i) {
swapped = false;
for (int j = 0; j < n - i - 1; ++j) {
if (a[j] > a[j + 1]) {
swap(&a[j], &a[j + 1]);
swapped = true;
}
}
if (swapped == false) {
break;
}
}

现在，最佳情况下的时间复杂度是O(n)，即当数组按升序排序时(在上述实现的上下文中)。平均和最坏的情况仍然是O(n^2)。

所以，为了确定你的算法的最佳时间复杂度，你必须向我们展示some O(n) stuff的实现，如果没有实现，那么至少展示你正在尝试实现的算法。

Answer 3

正如你所说的，它是O(n^2)。因为你做了n次O(n)的运算