Что такое Big O Нотация этой функции? - PullRequest
Новая
       15

Что такое Big O Нотация этой функции?

0 голосов
/ 18 октября 2018 
def scramble(s1, s2):
    arrs1 = list(s1)
    arrs2 = list(s2)

    if all(True if arrs2.count(item) <= arrs1.count(item) else False for 
item in arrs2):
        return True
    else:
        return False

Я пытаюсь создать функцию, которая может проверить, можно ли переставить часть символов строки (str1) в соответствии с другой строкой (str2).

Разве это не O (n)?

Ответы [ 3 ]

0 голосов
/ 18 октября 2018

Чтобы расширить ответ Ajax, ваш код без оператора all будет выглядеть примерно так: 

def scramble(s1, s2):
  arrs1 = list(s1)
  arrs2 = list(s2)

  are_counts_lte = []
  for item in arrs2:
    # this next "count" statement makes it O(n^2)
    if arrs2.count(item) <= arrs1.count(item):
      are_counts_lte.append(True)
    else:
      are_counts_lte.append(False)

  for b in are_counts_lte:
    if b is False: return False
  return True

Это явно O (n ^ 2) .

0 голосов
/ 18 октября 2018

Если вы хотите решение со средней сложностью по времени O (n), вы можете использовать collections.Counter вместо: 

from collections import Counter
def s(s1, s2):
    c1, c2 = Counter(s1), Counter(s2)
    return all(v <= c1.get(k, 0) for k, v in c2.items())
0 голосов
/ 18 октября 2018

Отправленный код на самом деле O(n^2): 

all(True if arrs2.count(item) <= arrs1.count(item) else False for item in arrs2)

all требует одного прохода по входу, что приводит к O(n) для сложности времени.Однако на каждом проходе число раз, item встречается в arrs2 и arrs1, должно быть получено.count имеет сложность O(n), так как объект списка должен быть итерирован, чтобы найти каждое вхождение нужного значения.Метод count вызывается дважды, однако он приблизительно равен O(n) как средняя сложность по времени.Следовательно, полное выражение: O(n)*O(n) => O(n^2).

...