2

这是计算十进制数的基本版本的代码。我不确定它的时间复杂度。谢谢， 

public static String convertToBase(int num, int base) {
    if (base > 36) {
        throw new IllegalArgumentException("The input argument should be less than or equal to 36.");
    }
    final StringBuilder sb = new StringBuilder();
    while (num > 0) {
        final int div = num % base;
        if (div > 9) {
            final int sum = div + 55;
            sb.append((char) sum);
        } else {
            sb.append(div);
        }
        num = num / base;
    }
    return sb.reverse().toString();
}
4

3 回答 3

2

严格来说，答案是O(1)。

如果int是支持任意精度的整数类型，那么答案显然是O(logN).

但事实并非如此！Anint可以不大于Integer.MAX_INT2^31 - 1 ... 或大约 20 亿。

因此，如果我们让N（无界整数）趋于无穷大，则 的值num将环绕，使其永远不会超过Integer.MAX_INT。这意味着如果（例如）baseis 10，while循环最多可以执行一次 log10(2^31)（即 10 次）......并且convertToBaseis O(1)。

但是，如果您准备滥用术语/符号，您可以说它O(logN)足够小N。

于 2013-07-15T08:39:05.947 回答
1

算法的复杂度是

IF Base=36, num=35......迭代次数为 1 IF Base=02, num=35......迭代次数是 6

这里迭代次数 = (num) 的对数，日志的基数 = 基数。

因此时间复杂度是大 O(Log(n))

于 2013-07-15T08:18:25.750 回答
1

正如 Stephen C 所说，复杂性是 O(1)，因为 n 是有界的。

如果 n 是任意精度数，则复杂度将为 O(M(n) log(n))，其中 M(n) 是乘法的复杂度（因为存在“num / base”操作）。

请参阅 http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Arithmetic_functions

于 2013-12-17T13:42:10.990 回答