Какова временная сложность этой функции Python?
def hasPairWithSum(arr,target):
for i in range(len(arr)):
if ((target-arr[i]) in arr[i+1:]):
return True
return False
В python сложность времени для этой функции O (n) или O (n ^ 2), другими словами, «if ((target-arr [i]) in arr [i + 1:])» — это еще один цикл for или нет? Также как насчет следующей функции, это также O (n ^ 2), если не почему:
def hasPairWithSum2(arr,target):
seen = set()
for num in arr:
num2 = target - num
if num2 in seen:
return True
seen.add(num)
return False
Спасибо!
Да, O (n ^ 2), потому что x в y выполняется Python как цикл.
Если вы создали s = set(arr) и использовали in s вместо in arr[i+1:], это было бы O (n)
@MarkMeyer, quamrana Спасибо за ответ, я отредактировал вопрос, не могли бы вы ответить на него. Спасибо!
@Moosefeather, как, можешь объяснить? Спасибо
@Neo, извините, я ошибся.
Ответы 2
Это О(n^2)
Первый цикл будет выполняться n раз, а второй будет выполняться (n-m) для каждого n. Таким образом, все это будет выполняться n (n-m) раз, то есть n ^ 2 - nm. Зная, что m<n, мы знаем, что его сложность равна O(n^2)
Но если это важно для чего-то, вы можете проконсультироваться с кем-то, кто лучше в этом разбирается.
m<n не является достаточным условием, чтобы заключить, что n²-nm равно O(n²). Например, если m=n-1, то n²-nm = n²-n(n-1) = n. Аналогично, если m=n-2, то оно будет равно 2n... и т.д.
Первая версия имеет временную сложность O(n²):
Действительно, arr[i+1:] уже создает новый список с n-1-i элементами, что не является операцией с постоянным временем. Оператор in просканирует этот новый список и, в худшем случае, посетит каждое значение в этом новом списке.
Если мы подсчитаем количество элементов, скопированных в новый список (с помощью arr[i+1), мы можем суммировать эти значения для каждой итерации внешнего цикла:
n-1
+ n-2
+ n-3
+ ...
+ 1
+ 0
Это треугольное число, равное n(n-1)/2, что равно O(n²).
Вторая версия
Вторая версия, использующая set, работает со средней временной сложностью O(n).
Здесь нет нарезки списка, а оператор in в наборе имеет, в отличие от аргумента списка, среднюю постоянную временную сложность. Итак, теперь каждое действие в цикле имеет (среднюю) постоянную временную сложность, что дает алгоритму среднюю временную сложность O (n).
Согласно документации python, оператор in для набора может иметь амортизированную наихудшую временную сложность O (n). Таким образом, вы все равно получите наихудшую временную сложность для вашего алгоритма O (n²).
Трикота спасибо большое!
if ((target-arr[i]) in arr[i+1:])— еще одна петля. Нужно сравнить каждый элемент спискаarr[i+1:]. Чтобы избежать этого, нужно создать набор, словарь или какую-либо другую структуру данных, позволяющую проводить тесты включения с постоянным временем.