Big O Notation Домашнее задание - анализ алгоритма фрагмента кода? [закрыто]

Question

Для домашней работы мне дали следующие 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

Answer 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. Извините, я не уловил это раньше.

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

<Ол>

Внешний цикл for, который начинается с 0-n

Еще один цикл for, который идет от 0 до 100

Некоторый код внутри, помеченный как ...

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

Удачи!