Анализ наилучшего случая, среднего случая, наихудшего случая и амортизированного случая
Я ищу понимание того, как все работает, а не просто ответ. Я даю то, что, как я думаю, ответ, но я не совсем уверен, и текст не имеет особого отношения к такого рода анализу.
Я прекрасно понимаю, что это НЕ то, как вы должны реализовывать стек, но это сценарий, который нам дали.
Часть А
Каково наихудшее, среднее и наилучшее время выполнения для вставки в слот [0] (несортированного) массива, содержащего N целых чисел, представляющих стек? Дайте тета границы.
Часть Б
Каково амортизированное время выполнения вставки N целых чисел в первоначально пустой массив a, представляющий стек, если каждая вставка происходит в [0]? Дайте точную оценку и объясните свой ответ.
Инструктор был совершенно уверен, что мы делаем все вставки в [0], и из этого "стека" нет удалений.
Мой анализ это
Предположение: длина a. N
Наилучшим случаем является Theta(1), который возникает, когда мы вставляем в пустой "стек".
Наихудший случай - тета (N), потому что как часть процесса вставки мы должны сместить N-1 элементов, чтобы освободить место на [0].
Средний случай также является тэтой (N), потому что, несмотря ни на что, мы всегда должны сдвигать N-1 элементов.
Амортизированный кейс
Каждая вставка стоит (N-1), и у нас есть N элементов, поэтому мы используем:
N
Sum (i) = [ N(N+1) ] / 2 = N^2 / 2 which is O(N^2) for N insertions
i=1
Амортизированная стоимость тогда будет N^2 / N = O(N)
Проблема у меня в том, что это выглядит легко. Я что-то упустил, или у меня почти ничего нет?