Большой O этого уравнения?

Question

 for (int j=0,k=0; j<n; j++)
   for (double m=1; m<n; m*=2)
      k++;

Я думаю, что это O (n ^ 2), но я не уверен. Я работаю над проблемой практики, и у меня есть следующие варианты:

• O (N ^ 2)
• O (2 ^ п)
• O (N!)
• O (n log (n))

Answer 1

Хммм ... ну, разбейте его.

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

Почему вы пришли к решению O (n ^ 2)?Докажи это.

Answer 2

Его O (nlog ₂ n) . Блок кода выполняется n * log ₂ n раз.

Предположим, n=16; Тогда первый цикл выполняется 16 (= n) раз. И второй цикл выполняется 4 (= log ₂ n) раз (m = 1,2,4,8). Таким образом, внутренний оператор k++ выполняется 64 раза = (n * log ₂ n) раз.

Answer 3

давайте посмотрим на худшее поведение.для второго цикла поиск продолжается от 1, 2, 4, 8 .... допустим, n равно 2 ^ k для некоторого k> = 0. в худшем случае мы могли бы закончить поиск до 2 ^ k и понять, что мы перешлицель.Теперь мы знаем, что цель может быть в 2 ^ (k - 1) и 2 ^ k.Количество элементов в этом диапазоне составляет 2 ^ (k - 1) (подумайте секунду).Число элементов, которые мы рассмотрели до сих пор, равно O (k), то есть O (logn), а для первого цикла это O (n) (слишком просто выяснить).тогда порядок всего кода будет O (n (logn)).

Answer 4

Общий способ решения подобных проблем - рассмотреть порядок каждого цикла, и, поскольку они вложенные, вы можете умножить нотацию "O".

Несколько простых правил для большого "O":

1. O(n)O(m) = O(nm)
2. O(n) + O(m) = O(n + m)
3. O(kn) = O(n) где 'k' - некоторая постоянная

Цикл 'j' повторяется по n элементам, поэтому очевидно, что это O (n). Цикл 'm' перебирает элементы log (n), поэтому это O (log (n)).

Поскольку циклы вложены, наш конечный результат будет O(n) * O(log(n)) = O(n*log(n)).