algorithm - 冒泡排序和分布排序算法的 "Problem size"是什么？

Question

已编辑:我之前提到过“输入大小”，但我指的是“问题大小”，我已经编辑了我的帖子。

有冒泡排序和分布排序两种算法，我认为冒泡排序的问题规模是“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”，但根据我的教授，这是错误的。我想知道冒泡排序和分布排序算法的问题规模的正确答案是什么？

Answer 1

这既是非常令人困惑的问题，也是非常令人困惑的答案。

在这两种情况下，您都需要所有输入，因此输入大小为 n，这也与复杂性理论相关，其中 n 具有与 相同的复杂性n-1 因此没关系。

并且在执行了多少次的情况下，冒泡排序执行到O(n^2)，分布排序分组了不止一种排序算法，但是没有排序更快比 O(n*log n)

PS:如果这是高中教授的话，很有可能他也没有完全理解复杂性理论。