Среди всех алгоритмов часто встречаются такие, которые что то делают с данными. И если входных данных много, то нам конечно же хочется чтоб он работал побыстрее. Но как измерить с какой скоростью выполняется алгоритм? Замерить время в секундах? Но ведь входных данных может быть разное количество, да и на разных компьютерах время будет разное. Посчитать сколько действий мы делаем во время работы алгоритма? Но ведь у него могут быть разные реализации, он может быть написан на разных языках программирования, а возможно у него вообще не будет реализации и он просто описан на словах.
Чтоб избежать всех этих проблем мы можем примерно оценить, насколько быстрее станет работать алгоритм если входных данных будет становиться все больше и больше.
Нарисуем график, где по оси n идет количество входных данных, а по оси t время за которое работает алгоритм. Синяя линия это график функции который показывает за какое время сработает алгоритм при каком то определенном количестве входных данных. Причем если алгоритм может иногда работать быстрее, а иногда медленнее, то мы выбираем самый медленный вариант. Затем нам надо подобрать красную функцию, так чтоб она всегда находилась максимально низко на графике, но при этом всегда была выше синей, и синяя никогда не уходила выше красной. Тогда зная красную функцию мы будем примерно представлять как себя ведет алгоритм.
Красная функция записывается как O(f(n)), и поэтому из за буквы "О" такая запись называется о-нотация.
Примеры
Рассмотрим некоторые часто встречаемые ситуации.
Допустим есть массив, и нам надо взять из него один элемент. Какого бы размера не был массив, элемент будет доставаться всегда за одно и то же время. Тогда мы запишем что то типа O(const).
Теперь попробуем сложить все числа в массиве. Для этого берем переменную равную нулю и по очереди добавляем к ней все числа. Тогда, сколько у нас есть элементов в массиве, столько действий нам и надо будет сделать, и мы запишем это как O(n).
Теперь возьмем все пары из двух чисел в массиве, какие только могут быть и выпишем их отдельно. То есть мы возьмем каждое число, и для него переберем все остальные числа. Количество действий будет равно количеству чисел возведенное в квадрат, и запишем мы это как O(n^2).
А что если у нас двоичный поиск числа в отсортированном массиве? Мы встаем в середину массива и смотрим, нужно число будет меньше чем число в середине или больше? Если меньше, то теперь уже левую половину массива делим пополам и проделываем ту же самую операцию, пока от массива не останется всего одно число. Количество таких делений будет равно log2(n), а это значит что даже если массив вырастет в два раза, количество действий увеличится всего лишь на единицу. Запишем это как O(log2(n)).