'if'in'時間複雜度

有人可以解釋下一個循環的時間複雜度嗎？'if'in'時間複雜度

for x in iterable: 
    if x not in other_iterable: 
     return False

我找到了一個很好的Python的運行時間複雜文本講座here，看到了外for循環時間爲O（N）。但是，if x not in other_iterable如何影響時間複雜性？我想象循環將檢查x對iterable中的每個元素，直到找到，或者列表已用盡。那麼建議如何讓if x not in other_iterable循環儘可能少的時間？可能已經整理了other_iterable？我在理解時間複雜性方面幾乎是一個新手，並且想知道更多。

編輯：other_iterable將是一個可能重複的列表。

來源

2017-03-07 ralston

這取決於。 'other_iterable'的數據類型是什麼？如果它是一個列表，它是O（N），但是如果它是一個集合，它是O（1）。（所以整個循環是O（N^2）（O，NM）或O（N），取決於） –

@JoranBeasley不，它不是，交集仍然是O（N）。（其中N是兩者中較小的一個） –

[Python中的\ *運算符中的\ *的複雜性]的可能重複（http://stackoverflow.com/questions/13884177/complexity-of-in-operator-in-python ） – Marat

在你叫他們的問題iterable，所以我將假設他們沒有set或相似，並且確定是否x not inother_iterable是真的，你有在同一時間檢查在other_iterable一個值。例如，如果它們是列表或生成器，則會是這種情況。

時間複雜度大概是最壞的情況;這是一個上限界限。所以，在這種情況下，最壞的情況是iterable中的所有內容都在other_iterable之內，但是是最後一個返回的項目。然後，對於iterable中的n項目中的每一項，您都將檢查other_iterable中的每個m項目，並且操作的總數將爲O(n*m)。如果n的尺寸大致相同，則爲O(n^2)。

例如，如果iterable = [8, 8, 8]和other_iterable = [1, 2, 3, 4, 5, 6, 7, 8]然後爲每個在iterable的3個項目，你必須檢查的8個項目中other_iterable，直到你發現你的if說法是假的，所以你不得不8 * 3總操作。

如果iterable中的第一項不在other_iterable中，最好的情況是。然後，您只會檢查iterable的一個元素，但是您會遍歷other_iterable中的所有m項，直到您獲悉if條件爲真，並且您完成。這總共是m的操作。但是，如上所述，大O時間複雜度是關於最壞情況的情況，因此您通常不會將此稱爲複雜性。

來源

2017-03-07 05:12:57

謝謝@OliverDain（同伴Wolfpack-er） – ralston

'if'in'時間複雜度

回答

相關問題