int num = n/4;
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
int count = 1;
}
}
}
Согласно книгам, которые я прочитал, этот код должен быть O ((n^3)/4). Но, видимо, его нет. найти Big-O для вложенных циклов, вы должны умножить границы? Таким образом, это должно быть num * n * n или n/4 * n * n.Поиск Big-O с несколькими вложенными циклами?
O((n^3)/4) не имеет смысла с точки зрения обозначения большого О, поскольку он предназначен для измерения сложности как отношения аргумента. Разделение на 4 не влияет, поскольку это изменяет значение отношения, но не его характер.
Все они эквивалентны:
O(n^3)
O(n^3/4)
O(n^3*1e6)
Другие термины имеют смысл только, когда они включают в себя n термин, например:
O(n^3/log(n))
O(n^3 * 10^n)
Как Энтони Kanago справедливо указывает, что это соглашение, по которому:
O(n^2+n) = O(n^2) ,O(n^2/4) = O(n^2).В целом, я не всегда согласен с этим первым правилом во всех случаях. Это правильное правило для определения максимальной скорости роста функции, но для таких вещей, как сравнение алгоритмов (a), где вы можете разумно установить ограничение на входной параметр, что-то вроде O(n^4+n^3+n^2+n) заметно хуже, чем просто O(n^4).
В этом случае любой термин, который зависит от входного параметра, должен быть включен. На самом деле, там могут быть полезны даже постоянные термины. Сравните, например, O(n+1e100) с O(n^2) - последнее будет довольно долгое время превосходить прежнее, пока n не станет достаточно большим, чтобы повлиять на константный срок.
(а) Есть, конечно, те, кто бы сказал, что не следует использовать таким образом, но прагматизм часто преодолевает догматизм в реальном мире :-)
Кроме того, n^3 + n включает в себя, что '+ n' как младший член, который можно отбросить. – Anthony
Спасибо, @ Энтони, я просто собрал несколько образцов, я должен был прочитать их немного внимательнее, прежде чем публиковать сообщения. – paxdiablo
Это верно, только если ваша фамилия не является «Кнутом» –
От http://en.wikipedia.org/wiki/Big_O_notation вы можете видеть, что константы, подобные 1/4, не играют роли для определения нотации Big-O. Единственный интересный факт состоит в том, что он n^3, таким образом, O (N^3).
Небольшая техничность. Нотация Big O предназначена для описания сложности в терминах «размера» ввода, а не числового значения. Если ваш ввод является числом, то размер ввода - это количество цифр вашего номера. Увы, ваш алгоритм O (2^N^3), где N - число цифр.
Ты потерял меня здесь, @token. «Размер» в этом цикле - это, очевидно, числовое значение, а не количество цифр (для чего требуется база данных-10 на n где-то). – paxdiablo
Формально, временная сложность может быть выведена, как в следующем:
п/4 * N * N = (п^3)/4 –
Смарт-компилятор, вероятно, оптимизируйте это гнездо цикла как O (1), так как оно фактически ничего не делает. – tgamblin
«Умный» компилятор оставил бы его в покое, если не сказать иначе - это может быть временная петля во встроенной системе, контролирующей скорость кровотока через диализную машину :-) – paxdiablo