编辑：我之前提到过"输入大小"，但我的意思是"问题大小"我已经编辑了我的帖子。
有两种算法气泡排序和分布排序，我认为气泡排序的问题大小为"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：如果这是来自高中教授，那么他很有可能也没有完全了解复杂性理论。
"问题大小"表示输入的大小。 算法的作用不会影响它。
当你认为BubbleSort的输入大小与DistributionSort不同的输入大小时，你的想法是错误的。 问题/输入的大小是问题/输入的大小。
当你试图弄清楚n或n-1是否正确时，你也思维错误。 我们甚至没有指定任何单位 - n 或 n-1 什么？ 在现实生活中的所有情况下，输入也占用了一些恒定的额外空间，我们甚至不计算这些空间。(堆栈帧指针等(
当我们不计算这些东西时，由于我们将如何在渐近符号的表达式中仅使用这个"大小"，因此n和n-1之间没有区别。