Домашнее задание о большой O-ноте - анализ алгоритма фрагмента кода?

Для домашней работы мне дали следующие 8 фрагментов кода для анализа и представления знака Big-Oh для времени выполнения. Может кто-нибудь, пожалуйста, скажите мне, если я на правильном пути?

//Fragment 1
for(int i = 0; i < n; i++)
    sum++;

Я думаю O (N) для фрагмента 1

//Fragment 2
for(int i = 0; i < n; i+=2)
    sum++;

O (N) для фрагмента 2, а также

//Fragment 3
for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

O (N ^ 2) для фрагмента 3

//Fragment 4
for(int i = 0; i < n; i+=2)
    sum++;
for(int j = 0; j < n; j++)
    sum++;

O (N) для фрагмента 4

//Fragment 5
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

O (N ^ 2) для фрагмента 5, но n * n отбрасывает меня, поэтому я не уверен.

//Fragment 6
for(int i = 0; i < n; i++)
    for( int j = 0; j < i; j++)
        sum++;

O (N ^ 2) для фрагмента 6 также

//Fragment 7
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        for(int k = 0; k < j; k++)
            sum++;

O (N ^ 3) для фрагмента 7, но снова n * n выбрасывает меня

//Fragment 8
for(int i = 1; i < n; i = i * 2)
    sum++;

O (N) для фрагмента 8

Ответы

Ответ 1

Я думаю, что фрагмент 5 есть O (n ^ 3), и аналогичным образом фрагмент 7 равен O (n ^ 5) *. Он также выглядит как O (log (n)) для фрагмента 8.

Для n * n задач вам нужно выполнить тело цикла n * n раз, поэтому это будет O (n ^ 2), тогда вы соедините это с порядком другого кода. Фрагмент 8 фактически удваивает счетчик вместо того, чтобы увеличивать его, поэтому чем больше проблема, тем меньше требуется выполнить дополнительную работу, поэтому O (log (n))

* edit: Фрагмент 7 равен O (n ^ 5), а не O (n ^ 4), как я думал ранее. Это связано с тем, что и j , и k идут от 1 до n * n. Извините, я не понял этого раньше.

Ответ 2

Фрагмент 7 равен O (n ^ 5), а не O (n ^ 4) в качестве принятых в настоящее время комментариев. В противном случае, это правильно.

Ответ 3

В случае 8 попробуйте записать количество итераций для некоторых значений N и посмотреть, как выглядит шаблон... это не O (N)

Ответ 4

Вы оказались на правильном пути. Что касается N * N, какой эффект, по вашему мнению, будет иметь? Это еще один фактор N, поэтому он, вероятно, будет более высокого порядка.

Просто предупреждение, я видел еще одну запись, как это, и она была крайне проголосована. Быть осторожен. Здесь - это сообщение.

Ответ 5

Вы на правильном пути, но вот подсказка о том, как все может стать яснее на этом пути. Предположим, у вас есть код:

for(i = 0; i < n; i++) {
   for(j = 0; j < 100; j++){....}
}

Правильно, учтите тот факт, что у вас есть код на разных уровнях. В этом примере вы можете видеть только 3 уровня:

  • Внешний для цикла, который идет от 0-n
  • Другой для цикла, который идет от 0-100
  • Код внутри, который помечен как ...

Ни в коем случае не пытайтесь вычислить все это в 1 раз. Именно здесь большинство новичков совершают какую-то арифметическую ошибку. Вычислите его индивидуально для каждого уровня, а затем умножьте все вместе.

Удачи!