Какова временная сложность этой функции NumberComplement?

Question

Функция NumberComplement (num) принимает десятичное число, преобразует его в двоичное число, затем инвертирует каждую двоичную цифру, а затем преобразует инвертированное двоичное число обратно в десятичное число.

мое решение

NumberComplement(num){ 
let bin= num.toString(2).split('').map(x => 1-x).join('') 
return parseInt(bin,2) 
} 

, что временная сложность для этой функции и почему?

(часть, которая меня смутила, является функцией карты, где num уже преобразован из целого числа в массив из 0 и 1, и мы знаем, что длина массива равна log (num) +1, поэтому функция итерации log (num) +1 раз, что делает сложность времени O (log (n))? ........ или я его переутомляю? Это просто O (n)?

Thank вы так много для вашего времени

Answer 1

Давайте предположим на секунду, что num может идти до бесконечности, то у вас есть эти вызовы функций, связанных:!.

| Function  | Asymptotic time complexity | Motivation                       | 
|--------------|----------------------------|------------------------------------------------------------------------------------------------------| 
| .toString(2) | O(log n)     | Number of bits in num                    | 
| .split  | O(log n)     | Number of characters from .toString, which is equal to number of bits in num       | 
| x => 1-x  | O(1)      | x is either 0 or 1 so this does not vary with the size of n           | 
| .map   | O(log n)     | The anonymous function applied to each element in the result from .split: O(1) * O(log n) = O(log n) | 
| .join  | O(log n)     | Number of characters in the result from .map, which is equal to the number of bits in num   | 
| .parseInt | O(log n)     | Number of characters in bin, which is equal to the number of bits in num        | 

Сложите их:

.toString + .split + .map + .join + .parseInt = 
O(log n) + O(log n) + O(log n) + O(log n) + O(log n) = 
O(log n) 

Это не верно в Javascript, однако, что есть верхняя граница 53 бита для целых чисел. С верхней границей на n вы всегда получаете асимптотическую сложность времени Big-O O(1).