Правильно ли этот худший случай?

Question

Вот код:

int Outcome = 0; 
for (int i = 0; i < N; i++) 
    for (int j = i+2; j = 0; j--) 
     Outcome += i*j; 

Вот мой анализ. Поскольку первая строка является оператором присваивания, это занимает ровно одну единицу времени, O (1). Пробой для строки 2: 1 + N + N = 2N + 2. С линией 3, , поскольку содержимое цикла является одной операцией, цикл и его блок выполняют операции i + 1. Это также вложенный цикл. Наконец, строка 4 принимает ровно одну единицу времени для выполнения. Поэтому для обозначения этого большого числа обозначений обозначается O (N).

Answer 1

Чтобы быть точным: как вы говорите, строка 4 - 1 операция. Для конкретного i вы выполняете внутренний цикл i+3 раз. Таким образом, ваше общее количество операций

sum(0 <= i <= N-1 : i+3) 
    = 3N + sum(0 <= i <= N-1 : i) 
    = 3N + N(N-1)/2 
    = N^2/2 + 5N/2 
    = O(N^2) 

Answer 2

Ваша интуиция верна о выпускном классе эффективности, но можно быть более строгим. Во-первых, вы обычно просто выбираете самую дорогую основную операцию, чтобы рассчитывать на анализ. В этом случае это, скорее всего, будет умножение во внутреннем цикле, которое выполняется один раз на итерацию. Итак, сколько раз это называется? На первой итерации самого внешнего цикла внутренний цикл будет повторяться дважды. На второй внешней итерации это будет три раза, и аналогично до N + 2 (я предполагаю, что условие внутреннего цикла должно быть j >= 0). Так что оставляет нас со следующим суммированием:

sum(2, 3, 4, 5, 6 ..., N+2) 
= sum(1, 2, 3, 4 ..., N+2) - 1 
= (N+2)(N+3)/2 - 1 

который находится в O (N²) (и на самом деле, так как у вас есть этот конкретный результат, который всегда будет то же самое можно сказать, что это в Q (N²)).