Расчет быстрой алгоритмической сложности

Question

Я знаком с материалом Big O и вообще знаю, как использовать критический раздел, чтобы выяснить сложность. Это один дает мне работу немного, так что я хотел бы ответ и небольшое объяснение:

i = 1; 
while(i<= n){ 
    if(i%2 == 0)(
    System.out.println(i); 
    } 
    i++; 
} 

Из того, что я понимаю, что тело из, если будет работать п/2 раз, потому что только даже я был бы распечатать. Так будет общая сложность: 1+ (n/2), что делает большой O O (n)? `

Answer 1

Общая сложность n + n/2 * (сложность System.out.println(i);). В этом случае, я думаю, вы можете предположить, что сложность вызова System.out.println является постоянной, поэтому общая сложность O (N). Важно заметить, что вы не можете игнорировать сложность итерации.

Answer 2

Общая сложность по-прежнему равна O (n), поскольку проверка значения i%2 и приращение i по-прежнему считается работой. Тело оператора if, которое выполняет n/2 раз, просто добавляет дополнительную O (n) сумму работы.

Answer 3

Вы неверно истолковали, что именно тело вашего кода (скорее, тело вашей петли). Это тело вашего кода (/ петли):

if (i%2 == 0) { 
    System.out.println(i); 
} 
i++; 

И это тело будет выполнено общим п раз, даже если половина времени условия if провалится.