Блог

Главная - Вопросы по программированию - В чем заключается большая сложность кода?

В чем заключается большая сложность кода?

#time-complexity #big-o

#временная сложность #big-o

Вопрос:

 for (int i = 1; i <= n; i  ) {
    for (int j = 1; j <= n; j  ) {
            j=j*2;
      }
}

У меня возникли проблемы с его обобщением.

Комментарии:

1. Подсчитайте количество итераций. Внутренний цикл не зависит от i того, что вы делаете j = j*2 и j на каждой итерации. Попробуйте это на бумаге, и вы поймете, что это достигается n примерно sqrt(n) за несколько шагов. ( 1, 3, 7, 15, 31, 63, ... ). Таким образом, каждый внешний цикл генерирует O(sqrt(n)) множество внутренних итераций. Внешний цикл выполняется n раз. Итак, у вас есть, O(n * sqrt(n)) что O(n^(3/2)) такое. j Это немного неприятно, но это не меняет того факта, что порядок величины по-прежнему остается O(sqrt(n)) , и это все, что имеет значение.

2. Это на самом деле log_2 и не sqrt , остальная часть аргументации все еще верна, хотя.

3. Обратите внимание, что, поскольку ваш код фактически ничего не делает, кроме изменения локальной переменной, компилятор может полностью заменить код ничем, поскольку он вообще не делает ничего, что влияет на внешнюю переменную. Таким образом, технически вы могли бы утверждать, что это может быть O(1) после оптимизации каким-то конкретным компилятором для определенного языка программирования.

Ответ №1:

Если мы посчитаем количество умножений, выполняемых программой, сложность будет n * log2(n)

Вы n умножаете внутренний цикл ( i масштабируется на n ), и внутренний цикл повторяется до тех пор, пока j <= n . j увеличиваться экспоненциально

 1, 3, 7, 15, 31, 63, 127, ... = (2^n) - 1

Что является 2^n масштабированием, поэтому удвоение значения n заставляет внутренний цикл повторяться еще раз.

 log2(n * 2) = log2(n)   1

Комментарии:

1. Не могли бы вы, пожалуйста, объяснить часть n * log2 (n)?

2. @RajeevR это уже объяснено. Я сказал, что вы выполняете еще 1 итерацию цикла j каждый раз, когда удваиваете значение n. Соответствующая функция этого поведения — log2(n). По мере повторения n раз количество итераций будет масштабироваться в соответствии с n * log2 (n). Однако я понятия не имею, что вы пытаетесь сделать.

3. Спасибо. Я просто решаю вопросы, чтобы найти большую временную сложность небольшого фрагмента кода. Это один из них. Спасибо, вы мне очень помогли.