已编辑:我之前提到过“输入大小”,但我指的是“问题大小”,我已经编辑了我的帖子。
有冒泡排序和分布排序两种算法,我认为冒泡排序的问题规模是“n-1”,因为操作执行了“n-1”次,而对于分布排序,我认为是“n”。但据我的教授说,他认为冒泡排序问题的大小是“n”,而分布排序问题的大小是“n-1”。我想知道我是对的吗?
我在网上查了一下,到处都说冒泡排序执行了“n-1”次,分布排序执行了“n”次操作,但我的教授说的恰恰相反,我无法理解他。如果我错了,谁能给我解释一下?
Bubble sort:
Algorithm1 BubbleSort(A[0..n – 1])
// Input: Array A[0..n – 1] of numbers
// Output: Array A[0..n – 1] of numbers sorted in non-decreasing order
do
swapped ← false
for i ← 0 to n – 2 do
if A[i] > A[i+1] then
swap (A[i], A[i+1] )
swapped ← true
while swapped
return A
Distribution sort:
// Input: Array A[0..n – 1] of numbers between L and U (with L ≤ U)
// Output: Array S[0..n – 1] of A’s numbers sorted in non-decreasing order
for j ← 0 to U – L do D[j] ← 0
for i ← 0 to n – 1 do D[A[i] – L] ← D[A[i] – L] + 1
for j ← 1 to U – L do D[j] ← D[j – 1] + D[j]
for i ← n – 1 down to 0 do
j ← A[i] – L
S[D[j] – 1] ← A[i]
D[j] ← D[j] – 1
return S
我预计冒泡排序的问题大小为“n-1”,分布排序为“n”,但根据我的教授,这是错误的。我想知道冒泡排序和分布排序算法的问题规模的正确答案是什么?
最佳答案
这既是非常令人困惑的问题,也是非常令人困惑的答案。
在这两种情况下,您都需要所有输入,因此输入大小为 n
,这也与复杂性理论相关,其中 n
具有与 相同的复杂性n-1
因此没关系。
并且在执行了多少次的情况下,冒泡排序执行到O(n^2)
,分布排序分组了不止一种排序算法,但是没有排序更快比 O(n*log n)
PS:如果这是高中教授的话,很有可能他也没有完全理解复杂性理论。
关于algorithm - 冒泡排序和分布排序算法的 "Problem size"是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57070181/