Блог

Я студент университета по специальности «Наука о данных», и в настоящее время мы обсуждаем сложность во времени. Я уже умел писать код на Python до учебы, но я никогда не уделял особого внимания эффективности времени и никогда раньше не изучал нотацию Big-O. Похоже, что во многих упражнениях я всегда близок к решению, но мой ответ никогда не бывает правильным.

Возьмем, к примеру, этот код на Python:

 def fun(N, M):  S1 = set(N)  S2 = set(M)  res = []  for x in S1:  if x in S2:  for i in range(N.count(x)):  res.append(x)  return res  

Скажем, длина N равна n, а длина M равна m. Мои рассуждения заключаются в следующем:

• for x in S1 в худшем случае O(n), потому что он повторяется в худшем случае n раз
• if x in S2 в худшем случае O(m), потому что в худшем случае он делает m сравнений
• N.count(x) равно O(n), потому что — в худшем случае — он выполнит n операций (при подсчете вхождений x в N)
• наконец .append() , операция выполняется n раз (как я уже говорил выше)

Если я прав, сложность должна быть O(n ³ м). Тем не менее, правильное решение-O(n ² m)

Можете ли вы помочь мне понять, где мои рассуждения терпят неудачу?
Извините, если мой вопрос может показаться очевидным или наивным, я не настолько опытен в мышлении в терминах сложности.

Вам нужно проверить сложность для всех линий:

 def fun(N, M):  S1 = set(N) # O(n)  S2 = set(M) # O(m)  res = [] # O(1)  for x in S1: # O(n) * ... SEE CORRECTION  if x in S2: # O(1)  for i in range(N.count(x)): # O(n) * ... SEE CORRECTION  res.append(x) # O(1)  return res # O(1)  

Затем сложите все вместе:

 O(n   m   1   n*(1 n*1)   1) = O(n**2   m)  

Исправление / тонкости:

N.count(x) так всегда O(n) , но это O(N) ... не O(n)*... так . * Сложность зависит от ценности N.count(x) , а не от ее сложности. Думайте об этом как:

 k = N.count(x) # O(n) for i in range(k): # O(k)*...  

вместо:

 for i in range(N.count(x)): # O(???)  

Тогда то, что я написал, является наихудшим случаем (хотя и с очень вводящим в заблуждение ярлыком), когда все элементы N разные. В этом случае for x in S1: это действительно O(n)*... так, но тогда k = N.count(x) = 1 для всех x это for i in range(N.count(x)): O(n) O(1)*... (не O(n)*... ) все еще приводит к O(n m 1 n*(1 n 1*1) 1) = O(n**2 m) .

Однако в лучшем случае, когда все элементы в N идентичны , существует только одно значение для x so for x in S1: is O(1)*... , но также k = N.count(x) = n и для этого уникального x . so for i in range(N.count(x)): O(n) O(n)*... теперь приводит к O(n m 1 1*(1 n n*1) 1) = O(n m) .

(Но обычно вам не следует сосредотачиваться на сложности в лучшем случае.)