平均案例大O和排序的影響

我正在研究確定String是否包含所有唯一字符的方法實現的時間複雜性。平均案例大O和排序的影響

基本，蠻力，方法是在同一時間通過String一個字符來迭代保持的HashSet看到字符。對於迭代中的每個字符，我們檢查Set是否已經包含它，如果是，則返回false。如果搜索到整個String，則返回true。作爲最壞情況的複雜度，這將是O(n)。平均情況是什麼？ O(n/2)？

如果我們試圖通過將String排序爲char數組來優化這個數組，它的效率會更高還是更低？排序通常需要O(n log n)，這比O(n)差，但排序的String允許更早檢測到重複字符（特別是對於長字符串）。

我們說最壞的情況是O(n^2 log n)，但是平均情況會好一些嗎？如果是這樣，那是什麼？

來源

2017-09-04 clicky

作爲一個簡單的評論，沒有'O（n/2）'這樣的東西，它總是「舍入」去除常量。 – Shirkam

答案取決於你所說的「人物」。如果你有256個字符，那麼對於任何長度爲257的字符串，答案是肯定的，所以你只需要檢查不超過256個元素，因此複雜度爲O（1）。如果你的字符集的大小是「非常大」（比輸入大小大得多），那麼字符基本上不會重複，所以你會發現一個重複的並且以大約爲零的概率進行解救。 –

@ n.m。你有一半是錯誤的。嚴格地說，這個比較時間成本是O（n），因爲它取決於字符串長度。確實，對於一個小的數據集，它可以縮短到一定的時間，但它不能算作真正的符號。 – Shirkam

在未排序的情況下，平均情況完全取決於字符串！在不知道/假設任何分配的情況下，很難做出任何假設。

一個簡單的情況下，對於具有隨機放置字符的字符串，其中，所述字符中的一個重複一次：

的用於被佈置在重複字符可能性的數量是n*(n-1)/2
它是概率恰好k步驟檢測到重複是(k-1)/(n-1)
它在最k步驟檢測的概率(k*(k-1))/(n*(n-1))，這意味着平均，你會發現它（大型n）在約0.7071*n ... [不完全]

對於使用不同的頻率發生，或者你就字符是如何分佈的字符串中的不同假設，你會得到不同的概率多個字符。

希望有人可以延長我的回答！ :)

如果字符串排序，那麼你不需要HashSet。

但是，平均情況仍然取決於字符串中字符的分佈：如果您在開始時獲得兩個aa，則效率非常高;如果你得到兩個zz，那麼你沒有贏得任何東西。

最糟糕的情況是排序加檢測重複，所以O(n log n + n)，或只是O(n log n)。

因此，由於在平均情況和最壞情況下都增加了複雜性，因此預先對字符串進行排序似乎不是有利的。

來源

2017-09-04 15:38:09

所以，你的答案是，隨機生成的字符串的時間複雜度是'O（n）'，不是嗎？ – Shirkam

帶有隨機字符串的最壞情況是'O（n）'，是 –

以k個步驟檢測到重複的概率不是（k-1）/（n-1）。例如k = 2，概率是2 /（n（n-1）），並且k = n，概率是2/n。（並且，對於這個問題的評論，這裏假定有無數個字符）。 –

平均案例大O和排序的影響

回答

相關問題