这三种算法的复杂度是多少？

Question

我周四有一个关于数据结构和算法的考试，去年的考试中有这个试题，你必须确定用 java 编写的三种算法的复杂性。你能帮我解决这些算法吗，也许能解释一下你的解决方案，那真的很棒。谢谢！

我的解决方案是：

AlgorithmOne: n*log(n) 第一个循环将运行与 O(n)，第二个循环运行s 与 log(n) 因为计数器变量在每个循环中加倍迭代。

AlgorithmTwo：不编译，如果没关系不会用标准的java编译器编译。由于 return 语句，它在 O(1) 中，因为这将在 1 次迭代后结束算法。

AlgorithmThree：for循环的复杂度是n，因为i++和n/2会变成n，递归的复杂度是O(n)，因为它会被执行n次。总结一下algorithmThree的复杂度应该是O(n)，因为递归函数没有和循环相连。

int algorithmOne(int n){
    int sum = 0;
    for(int i = 0; i < n/2; i++){
        for(int j = 1; j <= n/4; j= j *2){
            sum++;
        }
    }
    return sum;
}

int algorithmTwo(int n){
    int sum = 0;
    for(int i = 0; i < n/2; i++){
        for(int j = n; j > 1; j = j/2){
            sum++;
            return sum;
        }
    }
}

int algorithmThree(int n){
    int sum = 0;
    if(n>1){
        sum = algorithmThree(n-1)+1;
    }
    else{ 
        sum = 1;
    }
    for(int i=0; i < n/2; i++){
        sum = sum-1;
    }
    return sum;
}

Answer 1

正如您所分析的，前两个是正确的。但是对于第三个，你需要再看一遍这个递归调用，

    if(n>1){
        sum = algorithmThree(n-1)+1;
    }

只要n>1就会执行。当它达到基本条件即 n=1 时，for 循环将运行 n/2 次然后 return到前面的递归调用，然后再重复一遍，使得总复杂度为O(n*n)。

这三种算法的复杂度是多少？

What is the complexity of these three algorithms?

java

complexity-theory

time-complexity