Что такое большая буква этого цикла?
Как начинающий программист, мне всегда было трудно заметить сложность иногда простого кода. Код в вопросе:
k = 1;
while (k <= n){
cout << k << endl;
k = k * 2;
}
Сначала я думал, что сложность была O (log n) из-за строки k = k * 2, и я запустил код в качестве теста и отследил, сколько раз он зацикливался относительно размера n, что было относительно низкий даже для больших размеров n. Я также вполне уверен, что это не O (n), потому что это заняло бы намного больше времени, но я мог ошибаться, потому что именно поэтому я задаю вопрос.
Спасибо!
Решение
Это O (log n).
В каждой итерации k удваивается — это означает, что в (log n) итерациях она будет равна или больше n.
Другие решения
В вашем примере k не увеличивается на 1 (k ++), оно удваивается при каждом запуске, что пересекает цикл во время log (n). Помните, что логарифмы — это противоположная операция возведения в степень чего-либо. Логарифмы появляются, когда вещи постоянно уменьшаются вдвое или вдвое, например, k в вашем примере
Как вы предложили, приведенный пример будет O (log n) из-за того, что К умножается на константу независимо от размера N. Такое поведение также можно наблюдать, сравнивая необходимые обходы двух очень простых тестовых случаев.
Например, если n = 10Легко показать, что программа затем повторяла бы цикл 6 раз.
Тем не менее, если вы удвоите значение N чтобы n = 20для программы потребуется только еще один обход, в то время как вы ожидаете, что для программы с O (n) потребуется примерно в два раза больше обходов, чем в исходном тестовом примере.
Example: 1~9
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
Глубина дерева (или фокус на 1 2 4 8 …) всегда ⌊O (logn) ⌋ + 1, поэтому сложность O (log n)
detector