Как рассчитать среднюю асимптоту c времени выполнения в обозначениях Big-O?

Question

Пытаясь понять асимптотические обозначения c, которые, как я понимаю, используются для описания производительности алгоритма. Правильно ли я сказал, что есть худший, лучший и средний сценарий ios? Так, например, для следующего фрагмента кода, какова средняя асимптотика c времени выполнения в нотации Big-O?

for (int i = 0; i < size; i++)
{
    printf("%d\n", i);
}
for (int i = 0; i < size; i++)
{
    for (int j = 0; j < size; j++)
    {
        printf("%d\n", i + j);
    }
}

Будет ли это O (n ^ 2)?

Answer 1

Правильно ли я сказал, что есть сценарий наихудшего, наилучшего и среднего случая ios?

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

Будет ли это O (n ^ 2)?

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

Редактировать: пример, когда сложность среднего и лучшего случая различна:

for(var i = 0; i < len; ++i) 
  if(arr[i] == needle)
    return needle;

В лучшем случае это постоянная операция, ie O (1), если элемент найден сразу, а в худшем случае O (n) линейная операция - конкретно линейный поиск.

Answer 2

Правильно ли я сказал, что есть сценарий наихудшего, наилучшего и среднего случая ios?

Случай - это просто некоторое подмножество всех возможных входов, возможно, подмножество, которое имеет один ввод всех возможных размеров ввода. Так, например, для алгоритма сортировки может быть некоторое подмножество набора всех возможных входных массивов, а может быть только те подмножества, которые имеют ровно один элемент каждого входного размера. Используя это определение, наихудшим случаем будет подмножество входов, так что они заставляют алгоритм выполнять большинство инструкций для данного размера ввода; лучшим вариантом будет набор входов, которые требуют наименьшего количества шагов при каждом размере ввода; и средний случай будет похож на ожидаемое значение запущенных типов по всем возможным экземплярам для каждого размера (по простому определению, приведенному выше, средний «случай» на самом деле вовсе не является истинным случаем, скорее, как гипотетический случай).

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

Отправленный вами код всегда выполняет объем работы, пропорциональный квадрату size ' с ценностью. В этом смысле это O(size^2). Это также Омега и Тета size^2. Если алгоритм получает входные данные, размер которых в битах пропорционален размеру, то это истинная сложность. Если алгоритм получает значение size в качестве входных данных (представленное с использованием log(size) битов), то сложность фактически экспоненциальная - сложность в терминах size можно назвать псевдополиномиальной .