Я пытаюсь проанализировать наихудший порядок роста в зависимости от N для этого алгоритма:
for (int i = N*N; i > 1; i = i/2)
for (int j = 0; j < i; j++) {
total++;
}
Я пытаюсь проанализировать, сколько раз будет выполняться строка total++, просматривая внутренние и внешние циклы. Внутренний цикл должен выполняться (N^2)/2 раза. Внешний цикл я не знаю. Может ли кто-нибудь указать мне в правильном направлении?
Оператор total++; будет выполняться следующее количество раз:
= N^2 + N^2 / 2 + N^2 / 4 ... N^2 / 2^k
= N^2 * ( 1 + 1/2 + 1/4 + ... 1/2^k )
Количество членов в приведенном выше выражении = log(N^2) = 2log(N).
Hence sum of series = N^2 * (1 - 1/2^(2logN)) / (1/2)
= N^2 * (1 - 1/4N) / (1/2).
Hence according to me the order of complexity = O(N^2)
Внешний цикл будет выполняться со сложностью log(N), так как ряд уменьшается до половины на каждой итерации. Например, бинарный поиск.
Внешний цикл выполняется ровно 2LOG (base 2) N + 1 раз (преобразование с плавающей запятой в целое и удаление десятичных знаков). Если вы видите, что значение уменьшается как N^2,N^2/2 , N^2/4... 1...
Таким образом, общее количество запусков ++ равно,
Суммирование( x от 0 до int(2LOG (основание 2) N + 1)) N ^ 2/2 ^ x
для этого вопроса, поскольку внутренний цикл зависит от значения переменной, которая изменяется внешним циклом (поэтому вы не можете решить это, просто умножив значения внутреннего и внешнего циклов). Вам нужно будет начать записывать значения в a, а затем попытаться выяснить ряд, а затем решить ряд, чтобы получить ответ.
как и в вашем вопросе, будет работать total++..
n^2 + n^2/2 + n^2/2^2 + n^2/2^3 + .....
тогда, взяв n^2 общих, получим
n^2 [ 1 + 1/2 + 1/2^2 + 1/2^3 + ...]
решить эту серию, чтобы получить ответ
