О- большое

«Сколько времени необходимо для выполнения? Какова его сложность для текущих входных данных?»

〰️ Точное время работы алгоритма определить сложно, так как оно зависит от многих параметров.

〰️ Например, от скорости процессора, на котором запускается этот алгоритм.

Поэтому нотация «О-большое» используется не для оценки конкретного времени работы кода. Ее используют для оценки того, как быстро возрастает время обработки данных алгоритмом в привязке к объему этих данных(это оценка в худшем случае или оценка сверху)

🔹 В общем случае “О-большое” записывается так: О(*), где * — кол-во операций требуемое для выполнения алгоритма.

Примеры: О(n), O(log n), O(n^2), O(nlogn), O(nk)..

🔹 Определим сложность алгоритма сортировки пузырьком в худшем случае, то есть когда нам придется отсортировать каждый элемент. (Лучший случай, когда массив данных уже отсортирован)

〰️ В алгоритме используется 2 цикла:в каждом проходе внешнего цикла совершается серия обменов так, что наибольший элемент передвигается в конец массива перед элементом, который поместился туда на прошлой итерации.
Процесс происходит до тех пор, пока массив не будет отсортирован.

〰️ Внешний цикл в худшем варианте повторится N-1 раз, где N-кол-во элементов списка для сортировки), общее кол-во всех сравнений =(N-1)*N, а кол-во обменов = (N-1)*N/2, тогда сложность можно оценить как O(n^2) в худшем случае, в лучшем O(n)- пройдемся N раз по циклу и ничего не поменяем