Big-O сложность java

Question

Я новичок в Java, мой вопрос связан с большой сложностью.

Для а), это явно O(n^2) для вложенной петли.

for (int i = 0; i < n; i++) 
    for (int j=0; j < n; j++) 

однако, б), с суммы операции ++ в конце, и осложнений в вложенном цикле, значит ли это изменить его сложность Big-O на всех?

int sum = 0; 
for (int i = 1; i <= n; i++) 
    for (int j = n; j > 0; j /= 2) 
     sum++; 

Answer 1

Ну, вначале: нотация Big O не связана с языком программирования, она зависит только от реализации. Так что это не имеет никакого значения, если вы делаете петли на Java или любом другом языке (кроме нескольких оптимизаций, выполняемых интерпретатором/компилятором, который, однако, изменить ход выполнения программы)

Для вложенного цикла:

1) sum++ считается постоянной операцией со стоимостью 1. Поэтому его можно пренебречь. O(n * 1) = O(n)

2) Внешний контур остается примерно такой же, имеющим O(n-1), равная O(n) как постоянные точек всегда можно пренебречь в асимптотических расчетах.

3) Внутренняя петля принимает log2(n) шагов для завершения. На каждом шаге n сводится к его половине, поэтому умножение на 2 делает один шаг назад, что приводит к двоичному логарифму.

В целом, сложность O(n log2(n))

EDIT: забавная вещь: не один до сих пор не видел, что внутренний цикл имеет реальную сложность O(infinity) как разделение некоторого положительного числа не всегда больше, то 0 .. Или я здесь не прав?

Answer 2

В вашем втором примере первый for итерация n раз, а вторая итерация log2(n) раз, так как вы разделите j по 2 на каждой итерации. Следовательно, сложность O (n log2 n).

sum++ в последней строке не влияет на сложность.

Answer 3

Очевидно, что в вашем примере b) внутренний цикл делает меньше итераций, чем в a). Уменьшение итерационного счетчика на каждой итерации является, по существу, логарифмической (log2), поэтому O-сложность примера b) равна O(n log2(n)).

Заметим, что это не относится к Java - это было бы то же самое в любом другом языке :-)

Чирза,

Answer 4

Говоря с чисто компьютерной точки зрения науки, большой O (см определение), описывает наихудший сценарий. Это даже означает, что если вы используете половину внутреннего цикла, O (n^2) все еще применяется. Однако вы можете записать его как менее восходящую функцию.