Какой будет нотация Big O для следующих вложенных циклов?
for (int i = n; i > 0; i = i / 2){
for (int j = n; j > 0; j = j / 2){
for (int k = n; k > 0; k = k / 2){
count++;
}
}
}
Мои мысли таковы: каждый цикл равен O(log2(n)), так что это так же просто, как умножить
O(log2(n)) * O(log2(n)) * O(log2(n)) = O(log2(n)^3)
Да это верно.
Один из способов выяснить сложность вложенных циклов, границы которых не зависят друг от друга, состоит в том, чтобы работать изнутри наружу. Самый внутренний цикл работает O(log n). Второй цикл выполняется O(log n) раз и каждый раз работает O(log n), поэтому он работает O(log2 n). Наконец, крайний цикл выполняется O(log n) раз и выполняет O(log2 n) на каждой итерации, поэтому общая проделанная работа составляет O(log3 n). ).
Надеюсь это поможет!
log<sup>2</sup> n можно спутать с log log n.
- person Peter Lawrey; 23.01.2013
Да, ты прав.
Простой способ расчета -
for(int i=0; i<n;i++){ // n times
for(int j=0; j<n;j++){ // n times
}
}
Это пример простого вложенного цикла. Здесь Big-O каждого цикла O (n), и обычно он вложен так O (n * n), что является O (n ^ 2) фактическим Big-O. А в вашем случае -
for (int i = n; i > 0; i = i / 2){ // log(n)
for (int j = n; j > 0; j = j / 2){ // log(n)
for (int k = n; k > 0; k = k / 2){ // log(n)
count++;
}
}
}
Который находится во вложенном цикле, где каждый цикл Big-O равен O(log(n)), поэтому общая сложность будет O(log(n)^3)
Действительно, ваше предположение верно. Вы можете показать это методично следующим образом:
O(log2(n)^3). - person Subhrajyoti Majumder schedule 23.01.2013