Что такое o большое
Перейти к содержимому

Что такое o большое

  • автор:

Big O

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

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

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

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

Выбор структуры данных зависит от конкретной задачи: от вида данных и алгоритма их обработки. Разнообразные структуры данных (в .NET или Java или Elixir) создавались под определенные типы алгоритмов.

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

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

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

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

const nums = [1,2,3,4,5];

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

const nums = [1,2,3,4,5]; const firstNumber = nums[0];

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

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

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

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

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

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

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

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

const nums = [1,2,3,4,5]; let sum = 0; for(let num of nums)

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

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

Анализ

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

const sumContiguousArray = function(ary) < //get the last item const lastItem = ary[ary.length - 1]; //Gauss's trick return lastItem * (lastItem + 1) / 2; >const nums = [1,2,3,4,5]; const sumOfArray = sumContiguousArray(nums);

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

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

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

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

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

const hasDuplicates = function (num) < //loop the list, our O(n) op for (let i = 0; i < nums.length; i++) < const thisNum = nums[i]; //loop the list again, the O(n^2) op for (let j = 0; j < nums.length; j++) < //make sure we're not checking same number if (j !== i) < const otherNum = nums[j]; //if there's an equal value, return if (otherNum === thisNum) return true; >> > //if we're here, no dups return false; > const nums = [1, 2, 3, 4, 5, 5]; hasDuplicates(nums);//true

Мы уже знаем что итерирование массива это 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).

const nums = [1, 2, 3, 4, 5]; const searchFor = function (items, num) < //use binary search! //if found, return the number. Otherwise. //return null. We'll do this in a later chapter. >const hasDuplicates = function (nums) < for (let num of nums) < //let's go through the list again and have a look //at all the other numbers so we can compare if (searchFor(nums, num)) < return true; >> //only arrive here if there are no dups return false; >

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

Мышление в терминах Big O

  • Получение элемента коллекции это O(1). Будь то получение по индексу в массиве, или по ключу в словаре в нотации Big O это будет O(1)
  • Перебор коллекции это O(n)
  • Вложенные циклы по той же коллекции это O(n^2)
  • Разделяй и властвуй (Divide and Conquer) всегда O(log n)
  • Итерации которые используют Divide and Conquer это O(n log n)
  • big-o notation
  • алгоритмы
  • javascript
  • структуры данных
  • сложность алгоритма
  • сложность
  • бинарный поиск
  • JavaScript
  • Программирование
  • Алгоритмы

Что такое «O» большое в программировании?

Замечали ли вы, что одни программы выполняются дольше, чем другие? Причиной задержки может быть, например, используемый компьютер. Но предположим, что у вас хороший компьютер с мощным процессором. Тогда в чем причина?

Дело в том, что время выполнения написанной программы зависит от переданных входных данных.

Но как выяснить, эффективна ли программа? Есть ли способ это определить? Как проверить, при передаче каких входных данных программа работает лучше всего?

Прежде чем перейти к ответам, разберемся с тем, как вообще работает эффективная программа. И в этом поможет одна забавная история.

Однажды в компании, которой надоел медленный интернет, было решено провести ряд тестирований. Передачу данных из одного места в другое, находящееся на расстоянии 50 км, проводили одновременно двумя методами.

Один метод заключался в использовании почтового голубя, к лапке которого привязали USB-флешку.

Вторым методом было использование интернета в тех же целях, что и голубя.

Самое интересное заключалось в том, что голубь обогнал интернет. Но как?

Если голубю потребовалось время, чтобы добраться до места, независимо от размера данных, то время достижения интернет-сигнала меняется в зависимости от размера данных.

Перейдем к вычислительным сложностям

Вот две сложности, связанные с программированием.

  • Временная: время, необходимое для обработки входных данных.
  • Пространственная: количество места, требуемое для обработки входных данных.

Что такое нотация “О” большое?

Этот термин используется в программировании для описания вычислительной сложности алгоритма. В частности, он позволяет оценить, сколько времени требуется для запуска программы.

Проще говоря, термином “О” большое определяется, как время выполнения растет по мере увеличения входных данных.

  • Увеличение времени выполнения. Поскольку время, необходимое для выполнения программы, зависит от процессора компьютера, используется “О” большое, чтобы показать, как меняется время выполнения.
  • Ввод данных. Поскольку проверяется не только время, которое требуется для выполнения программы, но и ввод, в нотации “О” большое есть “n”, которое определяет количество элементов обрабатываемых входных данных. Поскольку время выполнения растет с увеличением размера входных данных, эту величину можно представить в виде O(n).
  • По мере увеличения входных данных. По мере увеличения входных данных программам иногда требуется больше времени для выполнения, что приводит к проблемам с производительностью. Поэтому разрабатываемую программу нужно проверять по мере увеличения входных данных.

Визуализированные примеры

O(1) не увеличивается с изменением размера входных данных. Таким образом, время обработки O(1) — величина постоянная независимо от того, какие входные данные были переданы.

Пример:

let names = ['Atit', 'mahesh', 'ramesh', 'kamlesh'];
let data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
function checkLength(data) return data.length;
>
console.log(checkLength(names)); // 4
console.log(checkLength(data)); // 10

В данном случае, независимо от того, какие входные данные были переданы, сложность останется равной O(1).

Линейная временная сложность означает, что время пропорционально входным данным. Время будет меняться в зависимости от входных данных.

Пример:

function print(array) for (var i = 0; i < array.length; i++) console.log(array[i]); 
>
>
print(names) //4 times
print(data) //10 times

Показывает производительность пропорционально размеру входных данных. O(n²) представляет наихудшую производительность.

Пример:

function testdata(data) data.forEach(function(items) console.log('values ', data); 
items.forEach(function(number) console.log('Marks', number); //
>);
>);
>
const test = [
['maths', 52],
['science', 65],
['english', 72]
]
testdata(test)

Логарифмическая | O(log n)

Логарифмическая сложность представляет время, необходимое для выполнения алгоритма, пропорциональное логарифму количества элементов (n) входных данных.

Пример:

function log(n) for (let i = 1; i < n; i = i * 2) const result = i; 
console.log(result);
>
>
log(4); //2

Для данной программы с любыми итерациями значение i = i*2. Поэтому на n-й итерации значение i= i*n и i всегда меньше размера самого цикла (N).

Следовательно, можно получить:

2^n < N
log(2^n) < log(N)
n < log(N)

Таким образом, наихудшая временная сложность такого алгоритма будет равна O(log(n)).

Отбросим константы

Существует вероятность того, что O(N) код быстрее, чем O(1) код для определенных входных данных. “О” большое просто описывает скорость увеличения. По этой причине мы отбрасываем константу, что означает, что O(3N) на самом деле O(N):

Можно отбросить не только константы, но и неглавные члены:

  • O(N3+N) → O(N3)
  • O(N+logN) → O(N)
  • O(2∗2N + 1000N100) → O(2N)

Как вычислить сложность?

Очевидно, что сложность различается в зависимости от структуры кода, используемого в алгоритме. Рассмотрим несколько примеров кода и их сложность.

Циклы (Loops)

  • Внутри цикла операторы повторяются n раз. Если для выполнения кода требуется сложность O(m), то внутри n раз повторенного цикла она будет равна n∗O(m) или O(n∗m).
for (let i in arr1) print(i);
>
  • Количество циклов будет равно 4, а выполнение кода внутри цикла равно O(1), поэтому суммарное выполнение будет равно O(4).

Вложенные циклы ( Nestedloops )

  • Если один цикл находится внутри другого цикла, сложность будет расти экспоненциально. Другими словами, если сложность простого цикла равна O(n), добавление еще одного цикла внутри этого цикла сделает сложность O(n²).
for (let i in arr1) print(i); 
for (let j in i) <>
>
  • Здесь сложность первого цикла равна O(5), поскольку количество массивов равно 5, поэтому вложенный цикл также выполняется с той же сложностью 5 раз, а значит, оба цикла будут O(5²).
  • Важные аспекты математики в науке о данных — «что» и «почему»
  • Решение алгоритмических проблем: Поиск повторяющихся элементов в массиве
  • 8 показателей эффективности классификации

О-большое

«O» большое и «o» малое (\mathcal<O>» width=»» height=»» /> и <img decoding=, если существует константа C > 0 , что для всех x из некоторой окрестности точки x0 имеет место неравенство |f(x)| \leqslant C |g(x)|;

  • f является «о» малым от g при x\to x_0, если для любого \varepsilon&gt;0найдется такая проколотая окрестность U_<x_0>» width=»» height=»» /> точки <i>x</i><sub>0</sub> , что для всех <img decoding=
  • x\to x_0

    Иначе говоря, в первом случае отношение | f | / | g | в окрестности точки x0 ограничено сверху, а во втором оно стремится к нулю при .

    Обозначение

    Обычно выражение «f является „O“ большим („о“ малым) от g» записывается с помощью равенства f(x) = O(g(x)) (соответственно, f(x) = o(g(x))).

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

    В частности, можно писать

    f(x) = O(g(x)) (или f(x) = o(g(x))),

    O(g(x)) = f(x) (или o(g(x)) = f(x))

    Другой пример: при x → 0 верно, что

    O(x²) = o(x),

    o(x) = O(x²).

    Вместо знака равенства методологически правильнее было бы употреблять знаки принадлежности и включения, понимая O( ) и o( ) как обозначения для множеств функций, то есть используя запись в форме

    x² + x³ ∈ O(x²)

    \mathop O(x^2)\subset o(x)

    x² + x³ = O(x²)

    \mathop O(x^2) = o(x)

    Однако на практике такая запись встречается крайне редко, в основном в простейших случаях.

    При использовании данных обозначений должно быть явно оговорено (или очевидно из контекста), о каких окрестностях (одно- или двусторонних; содержащих целые, вещественные или комплексные числа и т. п.) и о каких допустимых множествах функций идет речь (поскольку такие же обозначения употребляются и применительно к функциям многих переменных, к функциям комплексной переменной, к матрицам и др.).

    Другие подобные обозначения

    Для функций f(n) и g(n) при n → n0 используются следующие обозначения:

    Обозначение Интуитивное объяснение Определение
    f(n) \in O(g(n)) f ограничена сверху функцией g (с точностью до постоянного множителя) асимптотически \exists (C&gt;0), U : \forall (n \in U) \; |f(n)| \leq C|g(n)|
    f(n) \in \Omega(g(n)) f ограничена снизу функцией g (с точностью до постоянного множителя) асимптотически \exists (C&gt;0), U : \forall (n \in U) \; C|g(n)| \leq |f(n)|
    f(n) \in \Theta(g(n)) f ограничена снизу и сверху функцией g асимптотически \exists (C&gt;0), (C
    f(n) \in o(g(n)) g доминирует над f асимптотически \forall (C&gt;0) ,\exists U : \forall(n \in U) \; |f(n)| &lt; C|g(n)|
    f(n) \in \omega(g(n)) f доминирует над g асимптотически \forall (C&gt;0) ,\exists U : \forall(n \in U) \; C|g(n)| &lt; |f(n)|
    f(n) \sim g(n)\! f эквивалентна g асимптотически \lim_<n \to n_0>\frac = 1″ width=»» height=»» /></td>
</tr>
</table>
<p>где <i><b>U</b></i> — проколотая окрестность точки <i>n</i><sub>0</sub>.</p>
<h3>Основные свойства</h3>
<h4>Транзитивность</h4>
<p><img decoding=
  • f(n)=O(f(n))\!
  • f(n)=\Omega(f(n))\!
  • Симметричность

    •  f(n)=\Theta(g(n)) \Leftrightarrow g(n)=\Theta(f(n))

    Перестановочная симметрия

     \begin</p><div class='code-block code-block-13' style='margin: 8px 0; clear: both;'>
<!-- 13agladky -->
<script src=

    f(n)= O(g(n)) &amp; \Leftrightarrow &amp; g(n)=\Omega(f(n)) \\ f(n)= o(g(n)) &amp; \Leftrightarrow &amp; g(n)=\omega(f(n)) \end» width=»» height=»» />

    Другие

    Асимптотические обозначения в уравнениях

    \sum_<i=0></p>
<ul>
<li>Если в правой части уравнения находится только асимптотическое обозначение (например <i>n</i> = <i>O</i>(<i>n</i>²)), то знак равенства обозначает принадлежность множеству (<i>n</i> ∈ <i>O</i>(<i>n</i>²)).</li>
<li>Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при <i>x</i> → 0 формула <i>e</i><i>x</i> − 1 = <i>x</i> + <i>o</i>(<i>x</i>) обозначает, что <i>e</i><i>x</i> − 1 = <i>x</i> + <i>f</i>(<i>x</i>) , где <i>f</i>(<i>x</i>) — функция, о которой известно только то, что она принадлежит множеству <i>o</i>(<i>x</i>) . Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например, ^nO(n_i^2)» width=»» height=»» /> — содержит только одну функцию из класса <i>O</i>(<i>n</i> 2 ) .</li>
<li>Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило: <br /><i>какие бы мы функции не выбрали (в соответствии с предыдущим правилом) взамен асимптотических обозначений в левой части уравнения, можно выбрать функции вместо асимптотических обозначений (в соответствии с предыдущим правилом) в правой части так, что уравнение будет правильным</i>. <br />Например, запись <i>x</i> + <i>o</i>(<i>x</i>) = <i>O</i>(<i>x</i>) обозначает, что для любой функции <i>f</i>(<i>x</i>) ∈ <i>o</i>(<i>x</i>) , существует некоторая функция <i>g</i>(<i>x</i>) , такая что выражение <i>x</i> + <i>f</i>(<i>x</i>) = <i>g</i>(<i>x</i>) — верно для всех <i>x</i> .</li>
<li>Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с прдыдущим правилом. <br />Например: 4<i>n</i> 4 + 4<i>n</i> 2 + 1 = 4<i>n</i> 4 + Θ(<i>n</i> 2 ) = Θ(<i>n</i> 4 ) . Отметим, что такая интерпретация подразумевает выполнение соотношения 4<i>n</i> 4 + 4<i>n</i> 2 + 1 = Θ(<i>n</i> 4 ) .</li>
</ul>
<p>Приведенная интерпретация подразумевает выполнение соотношения:</p>
<p><img decoding=

    Почему при оценке сложности алгоритмов используют O-большое, а не o-малое?

    Просьба, если в ответе решите использовать высшую математику, переведите сразу на обыденный язык, чтобы все было понятно и не возникло новых вопросов.

    Отслеживать
    13.7k 12 12 золотых знаков 43 43 серебряных знака 75 75 бронзовых знаков
    задан 23 фев в 7:22
    Artur Vartanyan Artur Vartanyan
    1,166 4 4 золотых знака 17 17 серебряных знаков 40 40 бронзовых знаков

    Stack Overflow на русском — это сайт вопросов и ответов для профессиональных разработчиков программного обеспечения, энтузиастов программирования и системных администраторов. Сайт создан и управляется сообществом. — вопрос в заголовке более чем уместен, @Harry

    23 фев в 8:51

    @Kromster В результате в вопросе нет вопроса. Тогда логично вообще убрать требование к телу вопроса, и разрешить задавать вопросы, состоящие только из заголовка.

    23 фев в 9:02

    Не уверен в корректности с математической точки зрения, но o -малое выглядит более строгим требованием, чем O -большое, что влечёт трудности с практическим применением. Когда говорят, имеет сложность O(N^2) , то подразумевается, что сложность действительно может быть квадратичной. Когда говорят имеет сложность o(N^2) , то имеется ввиду, что сложность будет гарантированно лучше, чем квадратичная. Например для линейного поиска в массиве можно сказать, что он имеет сложность O(N) , но нельзя сказать o(N) . Можно сказать, что он имеет сложность o(N * log(N)) , но это сбивает с толку.

    23 фев в 9:15

    Иными словами, O -большое сразу наглядно демонстрирует худший случай, а o -малое показывает некоторую недостижимую границу, и не совсем очевидно, что на самом деле представляет из себя худший случай.

    23 фев в 9:42

    Ну и o -малое тоже используется при оценки алгоритмов. Хороший пример — это коллекции Map и Set в javascript. Спецификация языка требует, чтобы время доступа к элементу коллекции в среднем было сублинейным (24.1 Map Objects), т.е. в среднем имело сложность o(n) . В терминах O -большого это может быть сложность,например, O(1) , или O(log(n)) , или даже O(sqrt(n)) .

    23 фев в 10:22

    2 ответа 2

    Сортировка: Сброс на вариант по умолчанию

    O-большое — аналог нестрогого неравенства (≤),
    o-малое — аналог строгого неравенства (<).

    s = 0 for i in range(0, n): for j in range(0, n): s += i * j 

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

    В случае с o-малым нужно предъявить такую формулу, что сложность алгоритма будет строго меньше этой формулы. Например сложность этого алгоритма есть o(n 3 ) — он работает быстрее чем любой кубический алгоритм. Или o(n 2.1 ), o(n 2+ε ) для любого ε > 0, или o(n 2 log(n)), или ещё бесконечное число вариантов из которых нельзя выбрать один «самый подходящий».

    Аналогия на числах: есть формула -x 2 , оцените её максимальное значение.

    Простой ответ в терминах O-большого — -x 2 ≤ 0. Не превосходит. А в терминах o-малого оценку привести сложнее: -x 2 < 1, -x 2 < 0.1, -x 2 < ε(ε > 0). Если вы предъявляете конкретный ответ со строгим неравенством, сразу можно сказать что ваш ответ не самый лучший — ε можно разделить пополам и получить лучший ответ.

    Лучшего ответа нет вообще. Есть последовательность ответов, каждый лучше предыдущего. Поэтому строгое неравенство непрактично использовать при оценках сверху.

    Отслеживать
    13.7k 12 12 золотых знаков 43 43 серебряных знака 75 75 бронзовых знаков
    ответ дан 25 фев в 8:23
    Stanislav Volodarskiy Stanislav Volodarskiy
    29.7k 3 3 золотых знака 16 16 серебряных знаков 54 54 бронзовых знака
    о-малое — это не просто строго меньше, это строго меньше для любого положительного множителя
    25 фев в 13:38

    @PakUula, константа — деталь реализации. Есть определение o-малого через «верхний предел отношения равен нулю» — совсем без констант.

    25 фев в 13:48

    Совсем на пальцах

    о-малое — это не просто «меньше». Когда пишут, что сложность алгоритма — о(f) , то хотят сказать, что с ростом параметра алгоритма сложность растёт гораааааааздо медленнее, чем f . Там, на бесконечности, сложность алгоритма даже в микроскоп не разглядеть по сравнению с f . Ну или как песчинка по сравнению с галактикой. Очень-очень-очень намного-намного-меньше, короче.

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

    С практической точки зрения О-большое полезнее. Предположим, мы знаем, что два алгоритма имеют сложность о-малое от эн-в-кубе, o(n^3) . Что это нам даёт? Ничего. А если мы знаем, что у одного сложность O(n^2) , а у второго O(n*log(n)) ? Сразу ясно-понятно, что нужно брать второй.

    но как человек, которому в жизни довелось доказывать сложность алгоритма, я думаю, что причина использования О-больших в другом

    Тоже на пальцах, но чуть сложнее

    Чисто из общих соображений: на ваш вопрос «Почему при оценке сложности алгоритмов используют O-большое?» ответить невозможно, так как он неверен.

    При оценке сложности в специальной литературе, то есть не учебниках, используют и О-большое, и о-малое, и даже Омега-большую (Ω), омега-малую (ω) и Тета-большую (Θ). И даже используют знак ~ (тильда). Хуже того, для алгоритмов факторизации помимо О-Омега-Тета-тильда используют ещё и букву L .

    Да что там специальная литература! В Википедии местами используют не только О-нотацию. Например, в статье о рекуррентных соотношениях (в английском эта теорема получила уважительное название Master theorem) текст пестрит Тета-нотацией.

    И всё же, почему так широко используют О-большое? Чем О-большое удобнее о-малого? Давайте посмотрим на определение О-большого, для простоты взяв случай n ⟶ ∞ :

    введите сюда описание изображения

    Здесь U — окрестность бесконечности, то есть луч чисел n > N для некоторого N .

    Что же написано в определении о-малого?

    введите сюда описание изображения

    Видите в чём разница? В первом кванторе. Для О-большого стоит квантор существования, а для о-малого квантор всеобщности. Конечно же первый квантор доказывать гораздо проще: нашел константу C , доказал, что для всех достаточно больших n неравенство выполняется, и свободен! С квантором всеобщности дело гораздо веселее. Нужно доказывать, что |f(n)/g(n)| ⟶ 0 , то есть показать что там, на бесконечности, никаких выбросов быть не может. В большинстве случаев это шибко сложно, мало кто хочет с такой фигнёй связываться.

    введите сюда описание изображения

    Возьмём для примера теорему о распределении простых чисел

    Чебышов сравнительно элементарными средствами доказал в 1850-м году, что π(x) «болтается вокруг» x/ln(x) и нашел константы, которые ограничивают отклонения. Но тот факт, что эти константы равны единице, и асимптотически π(x) сливается с x/ln(x) доказали только спустя 50 лет, причём это потребовало введения Риманом такой ниипической пушки, как дзета-функция, и аггрессивного развития теории функции комплексной переменной.

    ИМХО, причина использования О-большого заключается именно в сложности доказательства теорем для о-малого.

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *