#python #time-complexity
Вопрос:
Вот некоторый код, который берет список целых чисел, чисел и целевое целое число, цель, и возвращает два целых числа в числах, которые складываются в цель:
def twoSum(nums, target):
pointer_stat = 0
pointer_run = 1
while pointer_stat < len(nums):
while pointer_run and pointer_stat < len(nums):
if nums[pointer_stat] nums[pointer_run] == target:
return [nums[pointer_run],nums[pointer_stat]]
pointer_run =1
pointer_run = 1
pointer_stat =1
print(twoSum(nums,target))
Мой вопрос в том, или, скорее, я хотел подтвердить, является ли вышеописанное O(n^2) временем выполнения?
Я рассуждаю так: у нас есть два указателя, которые будут указывать на каждое из целых чисел в списке, и оба указателя будут пересекать список один раз каждый (таким образом, сложность O(N)), и поскольку у нас есть цикл внутри цикла, мы умножаем O(N) и O(N), чтобы получить O(N^2)
А сложность пространства равна O(1).
Комментарии:
1. Здесь нет никаких указателей. Да, вы умножаете сложность
2. Мне действительно непонятно, почему вы считаете, что установка целочисленного счетчика является указателем, и как это влияет на сложность выполнения вложенных циклов
3. Вложенные циклы не всегда означают квадратичную сложность. Это зависит от проблемы. Вы касаетесь каждого входного номера только один раз? Тогда это линейно. Вы касаетесь всех входных номеров один раз для каждого другого входного номера? тогда она квадратичная. ‘
4. Я не понимаю этого @rdas. Если у вас есть вложенные циклы и вы используете значения только один раз, то… на самом деле я совершенно сбит с толку. Вложенная итерация все равно должна произойти и что- то проверить, даже если это поиск по набору O(1)
5. @rdas мы касаемся каждого входного числа один раз каждым из двух «указателей», поэтому оба указателя в худшем случае будут повторяться один раз по всем входным данным
Ответ №1:
Вы правы, но O(n^2)-это наихудшая временная сложность, поскольку вы включаете в свой цикл оператор return, который может привести к выходу из двойного цикла раньше.
Пожалуйста, обратите внимание, что вы можете захотеть
while pointer_run < len(nums) and pointer_stat < len(nums):
вместо
while pointer_run and pointer_stat < len(nums):
так как это может привести к тому, что вы не остановите свой цикл (меньше, чем связывает сильнее, чем «и») и будете работать бесконечно.
Комментарии:
1. Привет, Вгар, я знал, что это наихудший случай, и это то, что записывает Big O правильно? — Я понимаю вашу точку зрения о том, что цикл может разорваться раньше, если условие будет выполнено.
2. Обозначение Big O описывает поведение (растущих) функций упрощенным образом. Мы все еще можем различать лучший, средний и наихудший случай (каждый с большим O): это помогает, например, различать два линейных алгоритма поиска по телефонной книге. Пример: Alg. 1 останавливается после того, как он нашел запись, Alg. 2 каждый раз просматривает всю книгу. Теперь давайте поищем запись «А» (в лучшем случае). Мы видим, что наилучшая производительность Alg. 1-O(1) (немедленное попадание), а Alg. 2-O(n). Ваш алгоритм относится к последнему, поэтому вы можете определить наилучшую, среднюю и наихудшую производительность.
Ответ №2:
Вы действительно можете проверить это и убедиться в этом сами:
import matplotlib.pyplot as plt
x=[]
y=[]
n=[1]
def twoSum(nums, target):
pointer_stat = 0
pointer_run = 1
iterations = 0
while pointer_stat < len(nums):
while pointer_run < len(nums) and pointer_stat < len(nums):
if nums[pointer_stat] nums[pointer_run] == target:
return [nums[pointer_run],nums[pointer_stat]]
iterations =1
pointer_run =1
pointer_run = 1
pointer_stat =1
x.append(len(nums))
y.append(iterations)
return True
for i in range(100):
n.append(1)
twoSum(n,10000)
plt.plot(x,y)
plt.xlabel('N')
plt.ylabel('Iterations')
plt.show()
