void compute(int n) {
int h = n;
while (h > 1) {
for (int i = 0; i < n; i++) {
// do some operation
}
h = h/2;
}
}
Может кто-нибудь, пожалуйста, скажите мне, что такое сложность (Big O) этой функции n ??Сложность этой функции?
Это на самом деле спор между мной и моим другом. мой стенд: сложность O (n * log (n)) Подставка для друга: журнал (n)
Спасибо за ваши ответы.
Если это домашняя работа (и это звучит немного похоже на нее), то сначала вы должны попробовать себя.
В основном, чтобы получить complecity вы посмотрите на структуру функции, то есть петли, птичьи петли и т.д., и определить, как долго они работают, какие входы зависят и т.д.
В этом случае вы имеют только один вход, n. Локальная переменная h начинается с того же значения, что и n, так что это по сути то же, сложность, однако вам нужно отслеживать, как она используется.
У вас есть по существу два вложенных цикла здесь, один, который работает на п, еще один вокруг него, что приводит к ч вдвое сократить каждый раз, когда он бежать. Таким образом, эта функция находится в O (n · журнал n).
Второй цикл не работает до n/2. Попробуйте n = миллион. Второй цикл не будет работать полмиллиона раз. На самом деле я думаю, что это O
Согласен, это не n/2, поэтому я удалил (а затем отредактировал) его, но нет, это не корень, см. Ответ Botz3000. Попробуйте n = 1024, вы увидите, что вы получите 10 итераций для внешнего цикла, который является log_2 1024, а не √1024 (это будет 32). – Joey
Это помогает заметить, что h уменьшается с той же скоростью, что и остальные узлы в поиске двоичного дерева, который, как известно, работает в O (log n) – Botz3000
Это, как представляется, O (n.sqrt (п))
Внешний цикл, очевидно, п, а внутренний цикл SQRT (п).
РЕДАКТИРОВАТЬ: Внутренний цикл соответствует правилу log (n), так как число итераций равно x, где 2^x = n.
Я должен уточнить: поскольку внутренний цикл «уменьшается вдвое» каждый раз, это порядок n^(1/2), который совпадает с sqrt (n). –
А, я вижу. Моя ошибка, я ошибался в части n/2. Но, к сожалению, вы так же ошибаетесь в корне. См. Ответ Botz3000. – Joey
Я бы сказал, что в каждом прогоне h сокращается наполовину и n операций выполняется, это O (n * log n).
Некоторые операции:
O(x)
для цикла: потому п> = ч и полагая ч не будет изменен во время "некоторой операции":
O(n*x)
внешней во время цикла:
O(log(n)*n*x)
Ясно n * log (h).
Я немного шокирован тем, что существует так много разных ответов. : -O – Botz3000
Он сходится, медленно к одному :-). Также еще рано утром, мозги не могут работать должным образом:/ – Joey
Это не вопрос времени, это вопрос доступности cafeïne :) – Martijn