Является ли временная сложность фрагмента кода меньше, чем O (n ^ 2)?
Я новичок в алгоритмах и структурах данных. Поэтому я присоединился к LeetCode, чтобы улучшить свои навыки. Первая проблема состоит в том, чтобы предложить алгоритм, временная сложность которого меньше O(n^2). Я использовал фрагмент кода ниже. Решение было принято.
def twoSum(nums: List[int], target: int)->List[int]:
for x in range(len(nums)):
for y in range(x+1, len(nums)):
if nums[x] + nums[y] == target:
return [x, y]
return [0, 0]
nums = [1,2,3,4]
target = 7
twoSum(nums, target)
Но в худшем случае он повторяет N элементов (индексы -> [0,1,2,3]) в (N-1)/2 раза (внешний индекс: внутренние индексы -> 0: [1,2,3], 1 :[2,3], 2:[3]), похоже на O(n^2). Нет ли ошибки в моих рассуждениях? Или ошибка на LeetCode?
Это была функция. Я отредактировал код, чтобы было понятно.
Я не знаю, почему это было принято
Ни LeetCode, ни какой-либо другой сайт для упражнений по алгоритмам не могут реально измерить временную сложность вашего кода — они могут только сделать наилучшее предположение, основанное на его фактическом измеренном времени выполнения.
Ответы 1
Это O (n ^ 2). Вы можете легко рассчитать временную сложность вашего решения, что в основном является методом грубой силы для решения этой проблемы.
В худшем случае у вас есть сумма [n, n-1,..., 1], которая равна n * (n + 1)/2, что составляет O (n ^ 2).
Обратите внимание, что такие платформы на самом деле не могут рассчитать временную сложность, они просто устанавливают ограничение по времени в своей системе, которое никоим образом не является точным.
Существует простое решение этой проблемы с использованием Hashmap, которое дает вам решение O (n), надеюсь, вы сможете понять это самостоятельно.
Это не функция. Если бы это была функция, например
def myFunction(nums):, она была бы O(n^2)