时间戳

首页 > 解决方案 > 这三种算法的复杂度是多少？

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

问题描述

星期四我有一个关于数据结构和算法的考试，去年的考试中有一个考试题，你必须确定用 java 编写的三种算法的复杂性。您能帮我解决这些算法吗，也许可以为您的解决方案提供一个非常棒的解释。谢谢！

我的解决方案是：

算法一：n*log(n) 第一个循环将以 O(n) 运行，第二个循环以 log(n) 运行，因为计数器变量在每次迭代中加倍。

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

算法三：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;
}

标签： javatime-complexitycomplexity-theory

解决方案

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

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

只要 n>1，这将被执行。而当它达到基本条件即n=1时，for循环将运行n/2次，然后返回上一个递归调用，然后再次重复，这使得总复杂度为O(n*n)。

推荐阅读