Меня попросили решить задачу, в которой я нахожу отсортированную по убыванию тройку из массива целых чисел A, где 0<=i<j<k<n и A[i] > A[j] > A[k]. Мое решение грубой силы было O (n ^ 3), и после оптимизации я придумал следующий код, и я изо всех сил пытаюсь найти его временную сложность:
def getTriplet2(array):
i, j, k, n = 0, 1, 2, len(array)
while i < j < k < n:
if array[i] > array[j] > array[k]:
return array[i], array[j], array[k]
elif array[k] > array[j]:
if i == n - 3:
break
if j == n - 2:
i += 1
j = i + 1
k = j + 1
if k == n - 1:
j += 1
k = j + 1
else:
k += 1
else:
i += 1
j += 1
k += 1
@QuangHà Это неправильно. В худшем случае (который является строго монотонным возрастающим массивом и ) посещаются все отсортированные тройки различных индексов.
так что O(n^3 + 5)
= O(n^3)
Ответы, уже данные на этот вопрос, полностью отвечают на него, но если вы также ищете эффективное решение, вы можете выяснить, существует ли оно (и найти его) за линейное время. Ключ в том, чтобы найти элементы, которые могут существовать в середине тройки. Сначала вы можете пройтись по списку вперед, отслеживая самый большой встреченный элемент. В каждом элементе либо он является самым большим из встреченных, либо по крайней мере один из предыдущих должен быть больше, чтобы он мог быть средним элементом. Проделайте очень похожую процедуру в обратном порядке, отслеживая наименьший элемент. Кандидаты со средней тройкой нашли работу дважды.
По сути, вы посещаете все отсортированные тройки индексов в худшем случае, который будет монотонно возрастающим массивом ( i < j < k => A[i] < A[j] < A[k]
выполняется универсально).
Чтобы увидеть это, обратите внимание, что для такого типа ввода ветвь elif array[k] > array[j]:
условного оператора будет выполняться на каждой итерации. Эта ветвь выполняется в O(1)
.
Количество индексных троек в порядке возрастания — это количество индексных троек, состоящих из различных чисел, а именно O(n \over 3) = O(n^3)
.
Асимптотически ваше оптимизированное решение не работает быстрее грубой силы.
O(3n + 5) = O(n)