Блог

Главная - Вопросы по программированию - алгоритм подсчета двоичных цифр || prove big oh

алгоритм подсчета двоичных цифр || prove big oh

#algorithm

#алгоритм

Вопрос:

Является ли большой oh (Log n ) ? как я могу доказать это, используя суммирование 

   //Input: A positive decimal integer n
  //Output: The number of binary digits in n’s binary representation
  count ← 1
 while n > 1 do
 count ← count   1
 n ← ⌊n/2⌋ 
 return count

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

1. Я думаю, вы имеете в виду n > 0 . Я бы сказал, что это было O(log(N)^2) где N значение (при условии, что в нем не больше байтов, чем необходимо)

2. С момента возврата count = logN (приблизительно). следовательно, доказано

Ответ №1:

n Уменьшается следующим образом:

 n   n / 2   n / 4   n / 8   ....   8   4   2   1

Суммирование приведенных выше рядов 2^(log(n)) - 1 .

Теперь перейдем к вышеупомянутому вопросу. Количество выполняемых циклов равно количеству элементов, отображаемых в приведенных выше сериях = временная сложность алгоритма.

Количество элементов, отображаемых в приведенной выше серии, равно logn . Таким образом, временная сложность алгоритма O(logn) .

 Example:
n = 8; the corresponding series:
8   4   2   1 = 15(2^4 - 1) ~ 2^4 ~ 2^logn
Here, number of items in series = 4

therefore, 
time complexity = O(number of iteration)
                = O(number of elements in series)
                = O(logn)

Ответ №2:

Просто проверьте возвращаемое значение count . Поскольку это было бы ближе к logN , вы можете заявить, что TC является log(N) .

Просто подумайте обратным образом (математически):

 1 -> 2 -> 4 -> 8 -> ... N (xth value considering 0-indexing system)
2^x = N
x = logN

Ответ №3:

Вы должны учитывать, что большие числа используют больше памяти и требуют больше обработки для каждой операции. Примечание: временная сложность зависит только от того, что происходит для наибольших значений, а не для меньших.

Количество итераций, log2(n) однако, является стоимостью n > 0 и n = n / 2 пропорционально размеру целого числа. т. Е. 128-битный стоит вдвое больше 64-битного, а 1024-битный в 16 раз больше. Таким образом, стоимость каждой операции равна, log(m) где m — максимальное значение без знака, которое хранит количество битов. Если вы предполагаете, что есть фиксированные потерянные биты, например, не более 64 бит, это означает, что стоимость составляет O(log(n) * log(n)) или O(log(n)^2)

Если бы вы использовали BigInteger от Java, вот какой была бы временная сложность.

Ответ №4:

Сложность Big Oh может быть легко вычислена путем подсчета количества запусков цикла while, поскольку операции внутри цикла while занимают постоянное время.В этом случае N изменяется как-

 N,N/2,N/4,N/16.... ,1

Просто подсчет количества терминов в приведенной выше серии даст мне количество циклов runs.So,

 N/2^p=1       (p is number of times loop runs)

Это дает p = logN, следовательно, сложность O (logN)