Java中Integer.toBinaryString()的时间复杂度

Question

我想知道 Integer.toBinaryString() 的时间复杂度。

Answer 1

有两种方法可以看待这个问题：

• Integer.toBinaryString(n)产生一个长度为 的字符串ceiling(log2(n))。该计算所花费的时间大致与 成正比log(n)。

• 的最大值n是 2^31 - 1，并且该计算所花费的时间始终少于某个固定的常量时间。

事实上，大O复杂度的问题Integer.toBinaryString(n)没有数学意义。根据定义，大 O 复杂度是指当某些变量趋于无穷大时函数的行为。在这种情况下，唯一的变量 ( n) 无法做到这一点。