for (int i = 0; i < SIZE; i++)
{
if (list[i] > list[i + 1])
{
swap list[i] with list[i + 1];
i = 0;
}
}
我想确定这个算法的时间复杂度,在最坏情况下...我不理解为什么它是O(n^3)。
for (int i = 0; i < SIZE; i++)
{
if (list[i] > list[i + 1])
{
swap list[i] with list[i + 1];
i = 0;
}
}
我想确定这个算法的时间复杂度,在最坏情况下...我不理解为什么它是O(n^3)。
我对n = 10和n = 100进行了分析。比较的次数似乎是O(n3),这是有道理的,因为i平均被设置为0 n / 2次,所以它大约需要n2 *(n/2)次比较和递增运算来完成for循环,但交换的次数似乎只有O(n2),因为显然不需要更多的交换来对整个列表进行排序。最好情况下,当然是n-1次比较和0次交换。
对于最佳情况测试,我使用已经排序的n个元素的数组:[0...n-1]。
对于最坏情况测试,我使用一个反向排序的n个元素数组:[n-1...0]
def analyzeSlowSort(A):
comparison_count = swap_count = i = 0
while i < len(A) - 1:
comparison_count += 1
if A[i] > A[i+1]:
A[i], A[i+1] = A[i+1], A[i]
swap_count += 1
i = 0
i += 1
return comparison_count, swap_count
n = 10
# Best case
print analyzeSlowSort(range(n)) # ->(9, 0)
# Worst case
print analyzeSlowSort(range(n, 0, -1)) # ->(129, 37)
n = 100
# Best case
print analyzeSlowSort(range(n)) # ->(99, 0)
# Worst case
print analyzeSlowSort(range(n, 0, -1)) # ->(161799, 4852)
显然,这是一种在比较方面非常低效的排序算法。:)
好的.. 开始吧.. 在最坏的情况下,假设我们有一个完全翻转的数组..
9 8 7 6 5 4 3 2 1 0
每次交换时.. i 都会被重置为0。
让我们从翻转 9 8 开始:现在我们有了 8 9 7 6 5 4 3 2 1 0,i 被重置为零。
现在循环运行到2,我们再次翻转.. : 8 7 9 6 5 4 3 2 1 0 i 再次重置.. 但是要把 7 放到第一位,我们需要再翻转 8 和 7:7 8 9 6 5 4 3 2 1 0
所以循环次数如下:
T(1) = O(1) T(2) = O(1 + 2) T(3) = O(1 + 2 + 3) T(4) = O(1 + 2 + 3 + 4) 等等..
最后,对于在此情况下最大的第n项,其T(n) = O(n(n-1)/2)。如果有帮助或不清楚的事情,请评论。
很明显,仅使用for
循环的时间复杂度为O(n)。问题是,它会运行多少次?
每当进行一次交换时,循环就会重新开始。你将会为每个元素从其起始位置到达其在排序后的正确位置进行一次交换。对于一个反向排序的输入,这将平均进行n/2次交换,再加上每个元素的交换次数,得到另一个O(n)。这就是导致O(n^3)的原因。
O(n^2)
,而不是 3。 - Hanky Pankyfor (int i = 0; i < SIZE - 1; i++)
,否则当你尝试与list[i+1]
进行比较时,会出现索引错误。 - Shashank