Пример алгоритма, который имеет верхнюю границу наихудшего случая, нижнюю границу наихудшего случая и оценки наилучшего случая?

Question

Есть ли какой-либо алгоритм A, такой, что для множества примеров наихудшего случая S для A, A имеет худшую верхнюю границу и худшую нижнюю границу худшего случая? Более того, для некоторых наборов входных данных он должен иметь разные наилучшие оценки случаев, не равные каким-либо наихудшим границам.

Например, H является гипотетическим алгоритмом, для которого H имеет наихудшую верхнюю границу сверху Ο (n^3), наихудшую нижнюю границу Ω (n^2) и наилучшее время пробега Θ (n).

Сообщите мне, что вышеупомянутая ситуация действительно значима или нет?

Спасибо :)

Answer 1

Ниже приведено менее естественное, но, возможно, более удовлетворительное определение H. Эта функция вычисляет куб суммы входного списка довольно глупо.

def H(lst): 
    s1 = 0 
    for x in lst: 
     s1 += x 
    if s1 == 0: 
     return 0 
    elif len(lst) % 2 == 0: 
     s2 = 0 
     for x in lst: 
      for y in lst: 
       s2 += x * y 
     return s1 * s2 
    else: 
     s3 = 0 
     for x in lst: 
      for y in lst: 
       for z in lst: 
        s3 += x * y * z 
     return s3 

В лучшем случае находится Theta (n). Самая узкая наихудшая верхняя граница формы O (n^k) равна O (n^3). Самая узкая наихудшая нижняя граница формы Omega (n^k) - Омега (n^2).

Однако следует отметить, что сжатые граница любой форме на худшем случае Тета (е (п)), где F (2m) = т^2 и F (2m + 1) = т^3 ,

Answer 2

как вы описать его, выбрать любой квадратичный алгоритм сортировки, скажет пузырьковая сортировка:

• В худшем случае верхняя границы может быть названа O(n^3).

• Худший пример нижнего предела можно назвать Ω(n^2).

• Лучшее время случай работы можно сказать, что Θ(n), когда вход уже отсортирован и вы проверить это за один проход перед запуском алгоритма или использовать оптимизаций, которые оканчиваются алгоритм преждевременно в этом случае.