Вопросы асимптотического анализа

Question

Я нашел пару вопросов по geeksforgeeks.org, которые, похоже, не могут понять (№ 1 и № 3). Я надеялся, что кто-то может прояснить ответы на меня:

выяснить, является ли истина/ложь действительной или

1.Time Сложность QuickSort является Θ (п^2)

Я ответил верно, но это неверно , Зачем? Если quicksort имеет временную сложность O (n^2), и мы знаем, что Θ (g (n)) = {f (n), где c1 * g (n) < = f (n) < = c2 * g (n) и n> = n0}, то разве это не доказывает, что оно верно, так как c2 * g (n) - верхняя граница может быть равна f (n)?

2.Time Сложность QuickSort О (п^2) - истинный

3.Time сложность всех компьютерных алгоритмов можно записать в виде Q (1)

Это верно, но я не имею понимая, почему это так. Алгоритм поиска может иметь нижнюю границу Ω (1), предполагая, что мы находим то, что искали в первом элементе, но как это справедливо для ВСЕХ компьютерных алгоритмов, таких как алгоритм сортировки вставки, где наихудший случай - O (n^2)?

ссылка: http://www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/

Answer 1

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

И, конечно, нижняя граница времени работы любого алгоритма является постоянным временем (Ω(1)). Он не должен достигать этой нижней границы, но алгоритм должен быть запущен и должен иметь хотя бы одну операцию.

Answer 2

Временная сложность QuickSort равна Θ (n^2) ---- Это означает, что для каждого значения n время, затраченное алгоритмом на выход, равно , равному, функция f (n) = n^2. но мы знаем, что это не верно для быстрого сортировки, потому что мы знаем, что для некоторого ввода время выполнения быстрого сортировки может быть равно функции g (n) = nlogn. поэтому нам нужно указать, является ли это худшим, лучшим или средним случаем. Правильно сказать: «Худшая временная сложность quicksort равна Θ (n^2)».

«Сложность времени QuickSort - это O (n^2)» --- это означает, что для каждого входного значения n время работы алгоритма не более Функция f (n) = n^2. Это означает, что существует некоторый вход, для которого алгоритм имеет время работы, которое может быть меньше f (n) = n^2. Мы знаем, что наилучшая временная сложность quicksort равна g (n) = nlogn и g (n) < f (n). Поскольку это утверждение охватывает все случаи, поэтому утверждение истинно.

Точно так же правильно сказать «Временная сложность сортировки является Ω (NlogN)». Потому что это означает, что время работы алгоритма является по крайней мере NlogN и п^2> NlogN.

«Временная сложность всех компьютерных алгоритмов может быть записана как Ω (1)» --- здесь 1 представляет собой функцию постоянного времени. Из приведенного выше утверждения следует: для выполнения любых компьютерных алгоритмов нам нужно минимальное постоянное время. для всех компьютерных алгоритмов.