временная сложность для сортировки для стеков?

Question

Скажем, у меня есть следующий код псевдо:

while A is not empty and stack top of A is less than x: 
    pop A and push the returned value onto B 
push x onto A 
while B is not empty: 
    pop B and push the returned valued onto A 

говорят стеки A и B изначально пусты. Вставляйте n чисел с новым номером x каждый раз, используя приведенный выше алгоритм, что будет худшей временной сложностью.

Я был в состоянии получить, что этот алгоритм будет сортировать вставляя номера с длиной п от наименьшего (вверху) к величине (снизу), и в лучшем случае будет п, когда число вставленных уже отсортировано, от самого большого до самого маленького. Но я не понимаю, как худший случай может быть O (n^2).

Answer 1

Как вы поняли, этот алгоритм использует 2 стека для сортировки коллекции элементов.

На каждом шагу он выталкивает предметы из A и толкает их затем в B до тех пор, пока не будет найдено нужное место. Затем он выскакивает из B и толкает назад к А.

Это означает, что на этапе п, есть максимум 2 * (N-1) +1 операций.

Если начальная коллекция обратного отсортирован, это будет происходить при каждом введении, что делает сложность O (N 2 ).

Answer 2

Вставка n элементов без сортировки будет o (n). Поскольку каждый вид o (n), сумма O (n^2). Худший случай: номера представлены в обратном порядке.

Answer 3

Для каждой вставки наилучший сценарий - это когда StackTop [A]> x, то он просто нажимает x на A и B будет пустым. Таким образом, сложность времени o (1) для каждой вставки в лучшем случае. Таким образом, для п элементов O (N)

Теперь предположим, что элементы вставлены в порядке возрастания, то каждая вставка будет вызывать стека А быть опорожнен и положить в B.
После этой вставки х в А и затем положить стек B элементы в A popping и pushing один за другим. Для этого требуется o (n) для каждой вставки. поэтому для n вставки o (n^2).

Answer 4

В худшем случае:
позволяет брать пример ввода {1,2,3,4}
step1: (x=1)
первоначально A, B пустуют. поэтому по алгоритму A{1}, B{}.
step2: (x=2)
алгоритмом B={1}, A ={2}, а затем A={1,2}B={}.
step3: (x=3)
алгоритмом изначально B={2,1}A={3}, а затем A={3,2,1}B={}.
step4: (x=4)
алгоритма изначально B={1,2,3}A={4}, а затем A={4,3,2,1}B={} стоимости для каждого шага, где (2*(n-1))n является размером входных данных.
поэтому, если подвести итог Худший случай. Сложность времени: O (n^2)