在學習選擇排序時，我遇到了一種稱為賓果排序的變體。根據這本詞典進入
我們可以將這個運算式用于具有隨機分布資料和未知 m 的平均情況運行時間，Theta(nm)，作為平均型別 2 運行時間，它還直接為我們提供了基于我們如何改變 n 的大小。
在最好的型別 2 情況下，m 可能只是一些與 n 無關的常數值。如果我們有 m=Theta(1) 隨機分布的重復集群，那么最好的運行時間是 Theta(n*Theta(1))) = Theta(n)。例如，您會看到賓果排序的 O(2n) = O(n) 性能只有一個唯一值（一次查找查找值，一次將每個值交換到前面），并且這個 O( n) 如果 m 受任何常數限制，則漸近復雜性仍然成立。
然而，在最壞的型別 2 情況下，我們可以有 m=Theta(n)，而賓果排序本質上會轉化為 O(n^2) 選擇排序。這顯然是 m = n 的情況，但如果內回圈的運行時間預計隨著每次迭代而減少，n/m 是任何常數值，對于 Theta( n)，我們仍然看到 O(n^2) 復雜度。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/379982.html