Хитрая Большая-O сложность
public void foo(int n, int m) {
int i = m;
while (i > 100) {
i = i / 3;
}
for (int k = i ; k >= 0; k--) {
for (int j = 1; j < n; j *= 2) {
System.out.print(k + "\t" + j);
}
System.out.println();
}
}
Я полагал, что сложность будет O (logn).
Это как продукт внутреннего цикла, внешний цикл - никогда не будет выполняться больше чем 100 раз, таким образом, он сможет быть опущен.
То, в чем я не уверен, является выражением while, оно должно быть включено в Большую-O сложность? Для очень большого я оцениваю его, мог оказать влияние или арифметические операции, не имеет значения на том, какой масштаб, количество как основные операции и может быть опущен?
2 ответа
Цикл while равен O (log m) , потому что вы продолжаете делить m на 3 пока оно не станет меньше или равно 100 .
Так как 100 в вашем случае является константой, ее можно игнорировать, да.
Внутренний цикл равен O (log n) , как вы сказали, потому что вы умножаете j на 2 , пока он не превысит n .
Следовательно, общая сложность составляет O (log n + log m) .
или арифметические операции, независимо от масштаба, считаются основными операциями и могут быть опущены?
Арифметические операции обычно можно опустить, да. Однако это также зависит от языка. Это похоже на Java, и похоже, что вы используете примитивные типы. В этом случае можно рассматривать арифметические операции O (1) , да. Но если вы, например, используете большие целые числа, это уже не совсем нормально, поскольку сложение и умножение больше не O (1) .
Сложность O (log m + log n).
Цикл while выполняет log3 (m) раз - константу (log3 (100)). Внешний цикл for выполняется постоянное количество раз (около 100), а внутренний цикл выполняется log2 (n) раз.