Ну, для случайного числа n существует a, b такой, что 2^a <= n <= 2^b или просто k такой, что 2^(k-1) <= n <= 2^k - 1 (1).Мы знаем, что для любого числа, меньшего 2^n, нам нужно log(2^n) = n * log(2) = n бит для его представления (2).Например:
- 5: 4 <5 <8;нам нужно 3 бита для 4, 5 битов для 8 => нам нужно 4 бита для 5
- 23: 16 = 2 ^ 4 <23 <32 = 2 ^ 5;поэтому нам нужно 5 бит для представления 23 </li>
В заключение, для точного числа бит b для случайного числа n, мы можем использовать формулу:
b = floor(log(n)) + 1
Итак, обозначение big-O, которое мы будем использовать: O(floor(log(n)) + 1) = O(logn).
Дополнительная информация:
1) Я предположил, что это случайное, целое, положительное число(хотя это также легко обобщить для отрицательных чисел), что, я полагаю, является вашей проблемной ситуацией;для дробных чисел немного сложнее обобщить эту формулу
2) Запись логарифма относится к логарифму в базе 2