javascript - 这个 NumberComplement 函数的时间复杂度是多少？

Question

函数 NumberComplement(num) 接受一个十进制数，将其转换为二进制数，然后反转每个二进制数字，然后将反转后的二进制数转换回十进制数。

我的解决方案是

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

这个函数的时间复杂度是多少？为什么？

(让我感到困惑的部分是map函数，其中num已经从整数转换为由0和1组成的数组，我们知道数组的长度是log(num)+1，所以函数迭代 log(num)+1 次，这使得时间复杂度为 O(log(n))？.......还是我想多了？仅仅是 O(n) 吗？

非常感谢您的宝贵时间!

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 的上限，您总能得到 O(1) 的 Big-O 渐近时间复杂度。