這個函數的大-O是什麼使字符串中的單詞反轉

Question

我有一個簡單的函數reverseWords（），它表示字符串中的單詞。例如。 S =「這是一個字符串」的輸入給出「siht si a gnirts」的輸出

我想知道這個函數的大O是什麼。是O（N），O（N^2）還是O（N * M）？ O（N），O（N^2）或O（N * M）是否是O（N），O（N^2）或O（N * M）？

• O（N^2）因爲我們有一個嵌套的循環例如。 （N * M）與上述相同的原因，除了M被表示爲循環遍歷字符
• O（N）因爲.. 。我忘了解釋

Answer 1

這是O(N)。我假設你不確定的部分是：

for element in listA: 
    output.append(element[::-1]) 

這裏要注意的一點是，雖然我們確實有嵌套循環（超過listA及以上在它的每個元素的字符），字符的總數處理仍然只有O(N)。如果k是每個單詞中字母的平均數量，則可以將時間想象爲N/k（對於外部循環）* k（對於內部循環）= N。

更直接的（我會說好）的方法來分析它認爲，「我需要爲每個字符做什麼」？：

• 掃描了它在split()找字邊界
• 將其複製到一個新字符串，split()
• 追加新的字符串結果列表（實際上我們這樣做不是每個字符一次少，但上限是罰款大O）
• 提前迭代器超過listA（再次小於一次，每個字只有一次）
• 將其按相反順序複製到片中的新字符串中。
• 它包含字符串追加到output（每次一個字）
• 任何join()做（我邀請你，如果你願意調查，或者把我的話，它是O(total length of all strings)）。

因此，提供的列表追加，存儲器分配，和諸如此類的東西，都是攤銷O(1)，這在CPython的是這樣，則整體的時間複雜度是O(N)包括join()。

由於正確的術語是重要的，因爲它是O(N)它因此也是O(N^2)。