代码之家 › 专栏 › 技术社区 › Faisal Alzahrani

用Java计算程序的Big-O

complexity-theory big-o time java

-1

Faisal Alzahrani · 技术社区 · 6 年前

我只是想问一下这个项目的大O是什么。我想是 n/2 ,但我不确定。

public static boolean isPrime(int k) {
    if (k <= 1)
        return false;
    else if (k > 2 && k%2 == 0)
        return false;
    else 
    {
        for(int i = 3;i<=k/2;i+=2)
            if (k % i == 0)
                return false;
    }
    return true;
}

1 回复 | 直到 6 年前

Zabuzard Louis-Philippe Lebouthillier 6 年前

复杂性是 O(k) 这是 线性时间 。

在最坏的情况下执行 k 是一个 首要的 。然后您的算法将执行所有行,直到 return true; 。

尤其是您完全执行 for 产生的循环 (k / 4) - 3 迭代次数:

for (int i = 3; i <= k/2; i += 2)

所以你得到 O((k / 4) - 3) 这是 O(k) 。

推荐文章

user2082616 · 移动应用程序上的设备时间与服务器时间-最佳做法是什么

6 年前

RoRo88 · 无法使用“HH:mm E d MMM YYYY”模式分析DateTimeFormatter

6 年前

Maciej JaÅocha · 如何在java中生成在特定时间启动其他函数的函数[关闭]

6 年前

Anton Konikov · 转换为单一时区的日期[重复]

6 年前

MrEmper · Java-自动生成当前日期+用户输入时间

6 年前

R A · 尝试为我的HTML游戏创建最快时间的高分

6 年前

Chintan7027 · MYSQL以数字时间格式计算日期差

6 年前

user3725021 · 将字符数据帧列转换为分数时间

6 年前

Ramesh S · 如何按时间禁用当前日期?

6 年前

Faisal Alzahrani · 用Java计算程序的Big-O

6 年前