這種解決方案如何在句子O（N）中翻轉整個句子中的反向詞，然後對每個詞逆轉？

這是如何解決在一個句子O（N）倒車的話，當它的整個句子反向調用，然後在每個字反轉？

N =整體串 M =長度每個串

的長度豈不是O（N）+ O（N * M）？使用M來表示字符串的長度是否正確，因爲M對於每個輸入可能是不同的？

您正在重複使用N表示兩件事。真的應該有三個變量：

然後你的整個算法將運行在O(N + M*O)。但是，M*O始終會比N小，因爲字符串由單詞和將它們分隔開的空格組成。所以你可以簡化整個事情到O(N)。

2016-03-21 00:44:12 Blckknght

感謝您的答案如果原始輸入是list = ['foo'，'bar'，'hello'，'world']，並且我只翻轉每個單詞（而不是整個列表），那麼每個單詞的平均長度確實有幫助。答案是O（M * O），對吧？ –

實際上，'M * O == N'，因爲'O'（根據定義）'N/M'。 – chepner

'M * O'通常會在一般情況下略小於'N'，因爲原始字符串中的單詞之間會有空格。 – Blckknght

如果您使用N作爲整個字符串的長度，那麼您不應該使用N * M來表示反轉每個單詞，它只是N，因爲您要通過整個字符串本身兩次：一次扭轉它，並且一次扭轉單個單詞。

編輯：如果給你一個字符串列表，並且要扭轉名單其次是字符串本身的反轉的順序，那麼這將是O（N）+ O（L * M），其中N是數組中元素的數量，M是單詞的長度，因爲數組與單詞是分開的。您可以顛倒數組的順序而不顛倒單詞，這是與單詞分開的計算。當你翻轉單詞時，單詞的長度乘以你正在翻轉的單詞的數量。

2016-03-21 00:29:22

顛倒O（N）的整個列表與對整個列表O（N * M）中的每個字符串執行反轉不同嗎？我在這裏錯過了什麼？ –

你定義爲N是什麼？這是整個字符串的長度。你爲什麼用整個字符串的子串乘以整個字符串的長度？你正在尋找的第二個數字將更接近L * M，L是字符串的數量，M是每個的長度。然而，子字串數乘以字數將我們帶回原來的N –

啊，我明白了！謝謝你清理那個。假設原始輸入是這個字符串列表（list = ['foo'，'bar'，'hello'，'world']，整個列表的反轉是否爲O（N），然後是每個元素的反轉是O（N * M）？ –

看代碼做什麼：

棘手的部分是逆轉單詞。因爲這些單詞都是同一個句子的一部分，所以你可以將它們看作是對整個句子的另一遍遍。

這使得：

所以整個事情是O（3N），這是上）。

2016-03-21 01:00:50

回答