Смущение о записи большого О (конкретный пример)

Сегодня мы провели упражнение в классе, посвященном нотации Big-O. Вот одна из проблем:

void modifyArray(int a[], int size)
{   
    int max = a[0];
    for (int i = 1; i < size / 2; ++i)
    {
        if (max < a[i])
        max = a[i];
    }
    for (int j = 1; j <= size * size; ++j)
    {
        ++max;
        cout << max;
    }
}

Моя интуиция говорит мне, что f (n) = n/2 + n ²= O (n ²), но, по словам моего профессора, ответ просто O ( п). Может ли кто-нибудь объяснить мне, почему и когда мы просто меняем то, что мы считаем размером ввода?

Я понимаю, что это не вложенный цикл - это не то, что меня смущает. Я не понимаю, почему для данного входа size второй цикл рассматривается только как O (n). Единственный способ, которым я могу это понять, - это изолировать второй цикл, а затем переопределить размер ввода, просто используя n = размер ^ 2. Я на правильном пути?

Ответ 1

Если код, который вы представляете, представляет собой именно тот код, который ваш профессор комментирует, тогда он ошибается. Как записано, он выводит каждое число от 1 до size * size, что, безусловно, является O (n ^ 2), так как n = размер является разумным выбором.

Да, вы правы, что можете сказать что-то вроде "O (n), где n - это квадрат размера массива", но это осложнение без цели.

Как говорили другие, если удаляется cout << max, компилятор может оптимизировать цикл до одного назначения O (1), что означает, что другая функция O (n) диктует общую эффективность большого вывода, но это может быть не так - кто сказал, что вы даже разрешаете оптимизацию? Поэтому наилучшим способом описать эффективность "большой-O" является то, что "если оптимизация срабатывает, тогда O (n) else O (n ^ 2)" - нецелесообразно утверждать одно или другое, а затем скрывать ваши предположения, а последствия, если они ошибаются, в сноске.

Ответ 2

Рассмотрим следующий пример:

for (i = 0; i < N; i++) {
    sequence of statements
}
for (j = 0; j < M; j++) {
    sequence of statements
}

Первый цикл - это O (N), а второй цикл - O (M). Поскольку вы не знаете, что больше, вы говорите, что это O (max (N, M)).

В вашем случае N = размер /2 и M = размер * размер.

O (max (N, M)) становится O (max (размер/2, размер * размер)), который равен O (размер * размер). поэтому f (n) = O (размер ^ 2) = O (n ^ 2)

для проблемы, которую вы задаете; да, я думаю, что вы считаете правильным. переопределить размер ввода до просто n = размер ^ 2., который должен быть способ считать его O (n).

Ответ 3

На самом деле вторая петля может быть устранена.

Если вы не считаете вывод промежуточных терминов, то

It is equivalent to max += size*size.

Затем сложность кода сводится к O(size/2) ~ O(size).