big o notation что такое

«О» большое — простое объяснение с картинками

Бью Карнес — разработчик, ведущий YouTube-канал сайта freeCodeCamp.org, — в своей статье «Big O Notation — Simply explained with illustrations and video» попытался простыми словами объяснить нотацию большого «О».

Нотация «О» большое используется для выражения скорости алгоритма. Это важно при оценке как чужих алгоритмов, так и своих собственных. В этой статье я объясню, что такое «О» большое, а также приведу список наиболее часто встречающихся значений большого «О» и соответствующих этим значениям алгоритмов.

Время работы алгоритмов растет с разной скоростью

У моего сына Иуды есть много игрушек. Их просто миллиард! Даже удивительно, как быстро ребенок может собрать такое количество игрушек, если он первый внук для обеих ветвей семейного древа.

В общем, у Иуды проблема. Когда к нему приходят друзья и хотят поиграть с какой-то определенной игрушкой, ее поиски могут занять целую вечность. Поэтому ему нужен алгоритм поиска, который помог бы найти нужную игрушку как можно быстрее. Он пытается выбрать между двумя разными алгоритмами: простым и двоичным.

Выбранный алгоритм должен быть и точным, и быстрым. С одной стороны, двоичный поиск быстрее. А у Иуды зачастую бывает лишь 30 секунд на поиски — пока его другу не станет слишком скучно искать игрушку. С другой стороны, алгоритм простого поиска легче написать, и шансы сделать что-то неверно гораздо меньше. Ведь если друг найдет баги в его коде, это будет очень огорчительно! Чтобы подойти к делу с максимальной точностью, Иуда решает засечь время, за которое каждый из алгоритмов справится со списком из ста игрушек.

Давайте предположим, что проверка одной игрушки занимает 1мс. Если Иуде придется проверить все 100 игрушек путем простого поиска, это займет 100мс. С другой стороны, применяя двоичный поиск, нужно проверить всего 7 игрушек (log2 100 это примерно 7, мы здесь не будем вдаваться в точную математику), а значит, на это уйдет 7мс.

Но на самом деле в списке миллиард игрушек. Сколько времени будет работать алгоритм простого поиска, обрабатывая такой список? А сколько времени понадобится алгоритму двоичного поиска?

Время работы простого и двоичного поиска со списком из 100 элементов

Иуда запускает двоичный поиск со списком из 1 млрд. игрушек и на работу этого алгоритма уходит 30мс (log2 1000000000 примерно равен 30). «32мс! — думает он. — Сколько же времени понадобится при простом поиске? Двоичный поиск примерно в 15 раз быстрее простого, ведь алгоритму простого поиска понадобилось 100мс на список из 100 элементов, а алгоритму двоичного поиска — только 7мс. Значит, простой поиск со списком из 1 млрд. элементов займет 30мс*15 = 450мс, верно? Это намного меньше 30 секунд, за которые мой друг успеет устать». И Иуда решает воспользоваться алгоритмом простого поиска. Но был ли это правильный выбор?

Нет. Оказалось, что Иуда ошибся и, возможно, потерял своего друга навсегда. Время работы алгоритма простого поиска со списком из 1 млрд. элементов это не 450мс, а 1млрд. миллисекунд, т. е., 11 дней! Дело в том, что время работы двоичного и простого поиска возрастает не одинаково.

Время работы растет с разной скоростью! По мере увеличения количества элементов время работы двоичного поиска будет понемногу расти, но при этом время работы простого поиска возрастает очень сильно. То есть, когда число элементов в списке возрастает, двоичный поиск внезапно становится намного быстрее простого.

Так что Иуда ошибся, предполагая, что двоичный поиск всегда в 15 раз быстрее простого. Если брать список с 1 миллиардом элементов, двоичный поиск будет уже примерно в 33 миллиона раз быстрее простого.

Вот поэтому очень важно знать, с какой скоростью возрастает время работы алгоритма в зависимости от размера списка. И здесь выходит на сцену «О» большое.

«О» большое говорит вам, насколько быстр ваш алгоритм. Предположим, у вас есть список с размером n (т. е., у вас n элементов в этом списке). Простому поиску нужно проверить каждый элемент, поэтому ему понадобится произвести n операций. Время работы этого алгоритма, записанное при помощи нотации «О» большого, составляет O(n).

Где же, собственно, время? Где секунды? Здесь их нет. «О» большое не сообщает вам скорость в секундах. Эта нотация позволяет вам сравнивать количество необходимых операций. Она говорит вам о том, как быстро возрастает скорость работы алгоритма.

Давайте рассмотрим еще один пример. Двоичному поиску для проверки списка из n элементов нужно осуществить log n операций. Каково время работы алгоритма, записанное в нотации «О» большого? O(log n). В общем, принцип записи следующий:

Эта запись сообщает вам количество операций, которое осуществит алгоритм. Называется все это нотацией ««О» большое», потому что перед количеством операций ставится заглавная буква «О».

«О» большое описывает количество операций при наихудшем сценарии

Предположим, вы ищете пользователя в своей базе данных и при этом применяете алгоритм простого поиска. Вы знаете, что его скорость — O(n), то есть, в наихудшем случае вашему алгоритму придется проверить каждого пользователя в вашей базе данных. Но допустим, вы ищете пользователя с именем aardvark213, а он стоит первым в списке. Вашему алгоритму не придется проверять каждый элемент списка, потому что он найдет нужного пользователя с первой попытки. Итак, время, которое потребовалось алгоритму, это O(n) или O(1)? Ведь он нашел нужного пользователя с первой же попытки?

Время работы простого поиска в нотации «О» большое все равно O(n). В нашем случае алгоритм нашел искомое сразу. Это сценарий наилучшего случая. Но «О» большое описывает наихудший сценарий. То есть, можно сказать, что в наихудшем случае алгоритму придется по одному разу проверить каждого пользователя в базе данных, и на это уйдет время O(n). Это перестраховка: вы знаете, что скорость работы простого поиска никогда не будет меньше, чем O(n).

Самые распространенные варианты «О» большого

Вот пять вариантов «О» большого, которые встречаются чаще всего. Они отсортированы от самого быстрого к самому медленному:

Визуализация разного времени в нотации «О» большого

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

Первый алгоритм займет O(log n) времени. Вы можете осуществлять 10 операций в секунду. Чтобы нарисовать сетку из 16 ячеек, при времени O(log n) вам понадобится осуществить 4 операции (log 16 с основанием 2 это 4). То есть, у вас на это уйдет 0,4с. Что, если нужно нарисовать 1024 ячеек? На это потребуется log 1024 = 10 операций, т. е., 1с. Это первый алгоритм.

Второй алгоритм медленнее, его время выполнения O(n). Чтобы нарисовать 16 ячеек, понадобится 16 операций, а чтобы нарисовать 1024 ячейки — 1024 операции. Сколько это в секундах?

На графиках вы можете увидеть скорость всех алгоритмов, от самого быстрого до самого медленного:

Есть и другие варианты времени выполнения алгоритмов, но эти встречаются чаще всего.

Конечно, это упрощение. На самом деле вы не сможете так точно конвертировать время, записанное при помощи «О» большого, в количество операций, но это хорошая прикидка.

Заключение

Вот основные вещи, которые нужно усвоить:

Источник

Big O

Примечание. Сокращенный перевод, скорее пересказ своими словами.
UPD: как отметили в комментариях, примеры не идеальны. Автор не ищет лучшее решение задачи, его цель объяснить сложность алгоритмов «на пальцах».

Big O нотация нужна для описания сложности алгоритмов. Для этого используется понятие времени. Тема для многих пугающая, программисты избегающие разговоров о «времени порядка N» обычное дело.

Если вы способны оценить код в терминах Big O, скорее всего вас считают «умным парнем». И скорее всего вы пройдете ваше следующее собеседование. Вас не остановит вопрос можно ли уменьшить сложность какого-нибудь куска кода до n log n против n^2.

Структуры данных

Часто, выбирая ту или иную структуру, мы просто копируем общепринятое решение. В большинстве случаев этого достаточно. Но на самом деле, не разобравшись в сложности алгоритмов, мы не можем сделать осознанный выбор. К теме структур данных можно переходить только после сложности алгоритмов.

Здесь мы будем использовать только массивы чисел (прямо как на собеседовании). Примеры на JavaScript.

Начнем с самого простого: O(1)

Возьмем массив из 5 чисел:

Допустим надо получить первый элемент. Используем для это индекс:

Насколько это сложный алгоритм? Можно сказать: «совсем не сложный — просто берем первый элемент массива». Это верно, но корректнее описывать сложность через количество операций, выполняемых для достижения результата, в зависимости от ввода (операций на ввод).

Другими словами: насколько возрастет кол-во операций при увеличении кол-ва входных параметров.

В нашем примере входных параметров 5, потому что в массиве 5 элементов. Для получения результата нужно выполнить одну операцию (взять элемент по индексу). Сколько операций потребуется если элементов массива будет 100? Или 1000? Или 100 000? Все равно нужна только одна операция.

Т.е.: «одна операция для всех возможных входных данных» — O(1).

O(1) можно прочитать как «сложность порядка 1» (order 1), или «алгоритм выполняется за постоянное/константное время» (constant time).

Вы уже догадались что O(1) алгоритмы самые эффективные.

Итерации и «время порядка n»: O(n)

Теперь давайте найдем сумму элементов массива:

Опять зададимся вопросом: сколько операций на ввод нам потребуется? Здесь нужно перебрать все элементы, т.е. операция на каждый элемент. Чем больше массив, тем больше операций.

Используя Big O нотацию: O(n), или «сложность порядка n (order n)». Так же такой тип алгоритмов называют «линейными» или что алгоритм «линейно масштабируется».

Анализ

Можем ли мы сделать суммирование более эффективным? В общем случае нет. А если мы знаем, что массив гарантированно начинается с 1, отсортирован и не имеет пропусков? Тогда можно применить формулу S = n(n+1)/2 (где n последний элемент массива):

Такой алгоритм гораздо эффективнее O(n), более того он выполняется за «постоянное/константное время», т.е. это O(1).

Фактически операций не одна: нужно получить длину массива, получить последний элемент, выполнить умножение и деление. Разве это не O(3) или что-нибудь такое? В Big O нотации фактическое кол-во шагов не важно, важно что алгоритм выполняется за константное время.

Алгоритмы с константным временем это всегда O(1). Тоже и с линейными алгоритмами, фактически операций может быть O(n+5), в Big O нотации это O(n).

Не самые лучшие решения: O(n^2)

Давайте напишем функцию которая проверяет массив на наличие дублей. Решение с вложенным циклом:

Мы уже знаем что итерирование массива это O(n). У нас есть вложенный цикл, для каждого элемента мы еще раз итерируем — т.е. O(n^2) или «сложность порядка n квадрат».

Алгоритмы с вложенными циклами по той же коллекции всегда O(n^2).

«Сложность порядка log n»: O(log n)

В примере выше, вложенный цикл, сам по себе (если не учитывать что он вложенный) имеет сложность O(n), т.к. это перебор элементов массива. Этот цикл заканчивается как только будет найден нужный элемент, т.е. фактически не обязательно будут перебраны все элементы. Но в Big O нотации всегда рассматривается худший вариант — искомый элемент может быть самым последним.

Здесь вложенный цикл используется для поиска заданного элемента в массиве. Поиск элемента в массиве, при определенных условиях, можно оптимизировать — сделать лучше чем линейная O(n).

Пускай массив будет отсортирован. Тогда мы сможем использовать алгоритм «бинарный поиск»: делим массив на две половины, отбрасываем не нужную, оставшуюся опять делим на две части и так пока не найдем нужное значение. Такой тип алгоритмов называется «разделяй и влавствуй» Divide and Conquer.

Этот алгоритм основан на логарифме.

Быстрый обзор логарифмов

Рассмотрим пример, чему будет равен x?

Нужно взять кубический корень от 8 — это будет 2. Теперь посложнее

С использованием логарифма задачу можно записать так

«логарифм по основанию 2 от 512 равен x». Обратите внимание «основание 2», т.е. мы мыслим двойками — сколько раз нужно перемножить 2 что бы получить 512.

В алгоритме «бинарный поиск» на каждом шаге мы делим массив на две части.

Мое дополнение. Т.е. в худшем случае делаем столько операций, сколько раз можем разделить массив на две части. Например, сколько раз мы можем разделить на две части массив из 4 элементов? 2 раза. А массив из 8 элементов? 3 раза. Т.е. кол-во делений/операций = log2(n) (где n кол-во элементов массива).

Получается, что зависимость кол-ва операций от кол-ва элементов ввода описывается как log2(n)

Таким образом, используя нотацию Big O, алгоритм «бинарный поиск» имеет сложность O(log n).

Улучшим O(n^2) до O(n log n)

Вернемся к задачке проверки массива на дубли. Мы перебирали все элементы массива и для каждого элемента еще раз делали перебор. Делали O(n) внутри O(n), т.е. O(n*n) или O(n^2).

Мы можем заменить вложенный цикл на бинарный поиск*. Т.е. у нас остается перебор всех элементов O(n), внутри делаем O(log n). Получается O(n * log n), или O(n log n).

* ВНИМАНИЕ, во избежание Импринтинга. Использовать бинарный поиск для проверки массива на дубли — плохое решение. Здесь лишь показывается как в терминах Big O оценить сложность алгоритма показанного в листинге кода выше. Хороший алгоритм или плохой — для данной заметки не важно, важна наглядность.

Источник

Big O Notation

Asymptotic notations are used to represent the complexity or running time of an algorithm. It is a technique of defining the upper and lower limits of the run-time performance of an algorithm. We can analyze the runtime performance of an algorithm with the help of asymptotic notations. Asymptotic notations are also used to describe the approximate running time of an algorithm.

Types of Asymptotic Notations

Following are the different types of asymptotic notations:

Big Omega Notation( Ω)

Need of Big O Notation

We can use Big O notation to compare and search different solutions to find which solution is best. The best solution is one that consumes less amount of time and space. Generally, time and space are two parameters that determine the efficiency of the algorithm.

Big O Notation tells accurately how long an algorithm takes to run. It is a basic analysis of algorithm efficiency. It describes the execution time required. It depends on the size of input data that essentially passes in. Big O notation gives us algorithm complexity in terms of input size. For the large size of input data, the execution time will be slow as compared to the small size of input data. Big O notation is used to analyze space and time.

Big O notation gives us the growth of the time. Big O notation of a particular function gives us the order of the growth of that function. It is used to tell the relative efficiencies of algorithms in terms of space and time. It makes us understand the execution time and the main requirement of the function of increasing input size.

x0″ alt=»fxc.g(x) ; x>x0″ src=»https://habrastorage.org/getpro/habr/upload_files/310/d10/5f1/310d105f1610753c57f65da7b1d2eea5.svg» width=»118″ height=»20″/>

We can say that f(x) is O(g(x)). This is Big O Notation of f(x). In its notation, ‘O’ stands for the order of magnitude. Big O notation represents the upper bound of an algorithm running time. Upper bound means maximum running time. It represents the worst case of an algorithm time complexity that is the largest amount of time an algorithm can take to for execution.

Types of Measurement

Following are the different ways to measure the algorithm efficiency such as:

It is the average time required for the execution of an algorithm.

It is the maximum time required to execute an algorithm. It tells us how slow an algorithm can execute.

The best case is the minimum time required for the execution of an algorithm. It tells how fast an algorithm can execute.

Example

To understand the above cases, let’s consider an array:

If we want to search for 2 in an above array and on comparing we found that element in the first position. Then it would be the best case because it requires minimum time.

If we want to search for 6 in the above array. Then we need to perform a comparison with each value in the array and it will require maximum time. So it would be the worst case.

If we need to find element 4 in a given array, then it would require an average time to perform comparison or execution. So this would be an average case.

When we talk about Big O notation, we typically look at the worst case.

Working Principle

To understand its working principle, the following things must be remembered while calculating running time :

We will ignore constants when there is a product of multiple terms. Because the run time of constant is only unit time. For example, if we have a function

This function will execute ‘n’ times. So, in this function ‘n’ matters, not 8. So constant ‘8’ will be ignored from this function. In this way, the run time complexity of this function will be ‘On’

2. If the Big O is the sum of several terms then only keep the largest term and left the rest of the terms. For example, if we have :

In this, we have two terms. Among these two terms, we will select the largest term. So here, just ‘n’ is the largest term because 900 is a constant value. So, its complexity is ‘O(n)’. Similarly, if we have an expression like :

Then its complexity will be ‘O(n2)’.

3. In the case of unsimplified Big O expressions such as:

After dropping out constant values from these expressions, we have:

4. Certain terms will dominate in it. Big O notation will be in this order:

O(n) has the smallest order due to less running time as compared to others. As the size of ‘n’ terms increase, running time will increase. So, higher-order terms have high running time. So ignore the low order terms as ‘n’ increases.

Time Complexity Analysis

Time complexity is a mathematical technique of showing how the runtime of a function rises as the size of the input increases. Time complexity gives us an idea about how function scales as input to the function gets larger. When the input size is small, the function will take less time. In time complexity analysis, firstly we have to understand the following terms:

In this, the time taken to complete a function does not increase with size but it remains constant. Big O notation of a constant time is always one. If we have some function x=6*5; In this function, there is going to be no input to this function. So, its runtime is 1, and time complexity will be ‘O(1)’.

In this, as the size of the input increases, time increases linearly with size. If we have a linear function f(x)=3x-1. And the value of x is in the range of 0 to n. This function will execute for 0 to n values. So in this way, the complexity of linear time will be ‘O(n)’. The expression O(n) will be read as ‘’

In this, the time taken to complete a function increases with size in a quadratic manner. If we have a quadratic function f(x) = 5×2 + 4y + 1.Value of x and y in the range of 0 to n.

So the time complexity will be ‘O(n2)’.

Big O Notation Worst-Case Complexity

For all positive values of n, if g(n) is a function.

Where there exists constants c and n0, such that

To understand this, let us consider an example in which we have the following function:

The value of f(n) will always be less than and equal to g(n2). So this function will work in the following way:

Graph

Let us consider the following graph. In this graph, the x-axis represents input size (n) and the y-axis represents time growth (T) of an algorithm. Time growth (T) increases with input size(n). Suppose that f(n) is a particular function with respect to the input side in this graph. For representing the upper bound, we plot a function ‘c.g(n)’. The value of function f(n) will not go above ‘c.g(n)’. The value of f(n) is always less than or sometimes equal to c.g(n).

Example 1

Let us consider an array from 1 to 10

Firstly, a function will be defined which will take an array ‘A‘ and find the sum of elements in the array. Inside this function, variables will be initialized. For each value of ‘k’ in this array, elements will be going to add in the variable ‘total’. In this way, the sum of all elements will be found in this array.

Where ‘T’ is the time taken to run the function. Then coefficient will be taken out as

If we have two functions and one of them executes at constant time and the other one takes linear time. The first function will take O(1) and the second function will take O(n) time. On comparing these two functions, it can be concluded that the second function will take more time. O(1) is better than O(n) because it takes less time to execute.

Example 2

Let us consider another array

Now we will determine the time complexity and Big O notation without any experiment.

In above code, time taken to execute ‘total=0 ‘ is O(1) and it will also be same for ‘return total’.

Time taken to execute the entire function is

Example 3

Now let us consider another example in which we have taken the following array:

Now to find the Big O notation and time complexity of this function, the execution time will be analyzed. As the variable ‘total ‘ takes an equal amount of time at every time. So, it has time complexity as ‘O(1)’. And ‘return total’ will also have the same time complexity. Time taken will be

In the above expression, c2 is the fastest-growing term.

Example 4

Let us consider another example related to quadratic time. For this purpose, we consider a two-dimensional array that is:

In this array, we have a total of nine elements. As the number of columns is equal to the number of rows in this array so we have ‘n2’ elements in this array. Now we will define a function that will find the sum of elements of this array. Then define a variable ‘total’ and assign a value equal to zero. Then a double for loop will be executed. In the for-loop, variable ‘i’ represents the element in each row.

The fastest growing term in above expression is C2.

Space Complexity Analysis

In space complexity analysis, we take a look at how much memory or space is used. For this purpose, let’s consider an example. We have created the sum variable ‘S’ and assigned its value to zero. In for loop, we initialize a counter variable only at once for the entire loop. On looking at the inner variable ‘number=numbers[i]’, this will execute on every single iteration of this for a loop. Once this iteration is finished, memory will be freed for this variable. As this entire loop runs it’s not as if each of these number variables is going to persevere in memory. Space complexity will be only ‘O(1)’

Properties of Big O Notation

It has the following properties:

Application of Big O Notation

Following are the applications of Big O Notation:

It is used to quickly compare multiple functions in terms of their performance.

Also used to analyze the execution time of an algorithm

Источник