O() нотация рассчитана на то, сколько инструкций будет выполнено в худшем случае.Предположим, у вас есть программа, в которой есть следующий цикл -
for(int i = 0; i < n; i++)
{
//some operation
}
Так что этот цикл будет выполняться n раз.Таким образом, временная сложность будет O(n).
Теперь предположим, что ваша программа имеет два цикла for -
for(int i = 0; i < n; i++)
{
//some operation
}
for(int i = 0; i < n; i++)
{
//some operation
}
Итак, временная сложность будет O(n+n) или O(2n).Но в асимптотической или O() записи мы обычно игнорируем любую постоянную часть.Поэтому мы просто скажем, что временная сложность составляет O(n).
Теперь углубимся немного глубже.Предположим, у вас есть следующая программа -
for(int i = 0; i < n; i++)
{
for(int i = 0; i < n; i++)
{
//some operation
}
}
Итак, давайте посчитаем, сколько инструкций будет выполнено в конечном итоге.Это n*n или n^2.Таким образом, сложность времени будет O(n^2).Точно так же, если есть три или более вложенных цикла, мы просто посчитаем, сколько инструкций будет выполнено в конечном итоге.
Что теперь такое O(1)?- к настоящему времени вы должны понять - если общее количество инструкций равно 1 или любому другому постоянному числу, это O(1).
Что насчет O(logn) - возьмите бинарный поиск, например.В бинарном поиске мы разрезаем наш массив на две половины.Математически максимальное время, в течение которого бинарный поиск может выполняться по массиву длины, составляет logn.Таким образом, сложность нашего времени составляет O(logn)
Это некоторые основные приемы.Очевидно, что есть много вариантов.Но суть в том, сколько операций / инструкций будет выполнено в худшем случае.