Как я могу найти временную сложность следующего фрагмента?

Меня попросили решить задачу, в которой я нахожу отсортированную по убыванию тройку из массива целых чисел 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
O(3n + 5) = O(n)
Quang Hà 14.04.2023 02:43

@QuangHà Это неправильно. В худшем случае (который является строго монотонным возрастающим массивом и ) посещаются все отсортированные тройки различных индексов.

collapsar 14.04.2023 02:50

так что O(n^3 + 5) = O(n^3)

Quang Hà 14.04.2023 03:05

Ответы, уже данные на этот вопрос, полностью отвечают на него, но если вы также ищете эффективное решение, вы можете выяснить, существует ли оно (и найти его) за линейное время. Ключ в том, чтобы найти элементы, которые могут существовать в середине тройки. Сначала вы можете пройтись по списку вперед, отслеживая самый большой встреченный элемент. В каждом элементе либо он является самым большим из встреченных, либо по крайней мере один из предыдущих должен быть больше, чтобы он мог быть средним элементом. Проделайте очень похожую процедуру в обратном порядке, отслеживая наименьший элемент. Кандидаты со средней тройкой нашли работу дважды.

moreON 14.04.2023 03:28
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
4
66
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

По сути, вы посещаете все отсортированные тройки индексов в худшем случае, который будет монотонно возрастающим массивом ( i < j < k => A[i] < A[j] < A[k] выполняется универсально).

Чтобы увидеть это, обратите внимание, что для такого типа ввода ветвь elif array[k] > array[j]: условного оператора будет выполняться на каждой итерации. Эта ветвь выполняется в O(1).

Количество индексных троек в порядке возрастания — это количество индексных троек, состоящих из различных чисел, а именно O(n \over 3) = O(n^3).

Асимптотически ваше оптимизированное решение не работает быстрее грубой силы.

Другие вопросы по теме