Java 程序计算 (2^n) 的值；程序应该运行 with Big-O(2^n)

Question

这个java程序是用Big-O(2^n)运行的吗？如果没有，有什么修改建议吗？

这个程序计算2^n的值：

public static int exponent(int n) {
    if (n == 0)
        return 1;   
    else
        return 2 * exponent(n - 1);
}

Answer 1

好消息：它在 O(n) 中运行。

每次迭代，n 递减 1，因此它正好循环 n 次

Answer 2

是的，它甚至在 O(n) 中，因此也在 O(2^n) 中。

Answer 3

该算法具有 O(n) 时间复杂度。如果添加第二个参数，则可以创建一个时间复杂度为 O(log n) 的方法。

public static int power(int base, int n) {
    if (n == 0)
        return 1;
    else if (n % 2 == 0)
        return power(base * base, n/2);
    else
        return base * power(base * base, n/2);
}

在您的代码中，n 每次都会减少 1，因此需要 n 步才能终止。使用这种方法，n 每次都会减半，因此可以更快地完成。

Answer 4

要有一个与解决方案成正比的大 O，它应该减少到 1，即它应该进行与答案一样多的调用。

因为有O(2^n)的时间复杂度

public static int power(int base, int n) {
    return n == 0 ? 1 : multiply(base, power(base, n -1);
}

public static int multiply(int a, int b) {
    return a > 0 ? add(multiply(a - 1, b), b) : 0;
}

public static int add(int a, int b) {
    return a > b ? 1 + add(a -1, b) : b > 0 ? 1 + add(0, b -1) : 0;
}

要计算 2^n 它将减少到 1 + 2^n 次。

Java 程序计算 (2^n) 的值；程序应该运行 with Big-O(2^n)

Java program to compute the value of (2^n); the program should run with Big-O(2^n)

java

algorithm

divide-and-conquer

Java 程序计算 (2^n) 的值；程序应该 运行 with Big-O(2^n)

Java program to compute the value of (2^n); the program should run with Big-O(2^n)

java

algorithm

divide-and-conquer

Java 程序计算 (2^n) 的值；程序应该运行 with Big-O(2^n)