我正试图找出k的哪些值为按升序对列表中的数字进行排序的算法提供了线性时间复杂性。我发现k的O(1(值使算法成为O(n(，但我听说k的其他值存在，我找不到。伪代码粘贴在下面。任何帮助都将不胜感激！
""" PSEUDOCODE
Function sort(a)
A <- new dict
K <- new array
M <- new array
For i in a
A.add {i:0}
For i in a
A[i] <- A[i]+1
For key in A.keys
K <- add key
K <- Quicksort (K)
For k in K
M = M + [k]*A.value(k)
return M
"""
您的前3个循环是O(a(到目前为止的O(3a(
快速排序是O(alog(a((最好/平均，O(a^2(最差(表示为QS(
第四个循环是O(a(
总之：
O(3a(+O(QS(+O(a(
=O(4a(+O(QS(
=O(a(+O(QS(
=O(QS(