gpt4 book ai didi

java - 时间复杂度

转载 作者:行者123 更新时间:2023-12-02 03:49:07 25 4
gpt4 key购买 nike

我正在尝试找出这些过程的时间复杂度,但我不确定它们是否好。

我认为这是 O(n)

static void P1(int n ){
for (int i=1; i<=n; i++) {
Procedure();
}

我认为这是 O(n^2)

static void P2(int n) {
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
Procedure();
}

O(n)+O(n)

static void P3(int n) {
for (int i = 1; i <= n; i++)
Procedure();
for (int i = 1; i <= n; i++)
Procedure();
}

100+n+100?

static void P4(int n) {
for ( int i = 1; i <= 100; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= 100; k++)
Procedure();
}

O(n*i)?

static void P5(int n) {
for ( int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
Procedure();
}

static void P6(int n) {
for (int i = 1; i <= n/2; i++)
for ( int j = 1; j <= n/4; j++)
for (int k = 1; k <= n/8; k++)
Procedure();
}

最佳答案

如果 procedure() 的复杂度为 O(1),则:

我认为这是 O(n) 正确

static void P1(int n ){
for (int i=1; i<=n; i++) {
Procedure();
}

我认为这是 O(n^2) 正确

static void P2(int n) {
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
Procedure();
}

O(n)+O(n) 正确,但是 O(n+n)=O(2n)=O(n)

static void P3(int n) {
for (int i = 1; i <= n; i++)
Procedure();
for (int i = 1; i <= n; i++)
Procedure();
}

100+n+100? 假,相乘:O(100*n*100)=O(n)

static void P4(int n) {
for ( int i = 1; i <= 100; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= 100; k++)
Procedure();
}

O(n*i)? 你不能使用它它没有确切的值。如果你看一下内循环执行了多少次,就是1+2+3+4+...+n-3+n-2+n-1,也就是n *(n-1)/2,您可以将其相乘:n*(n-1)/2=n^2/2-n/2 渐近 n^2/2-n/2=Theta(n^2)

结果为 O(n^2)

static void P5(int n) {
for ( int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
Procedure();
}

n/2 * n/4 * n/8 = n^3/64 = O(n^3)

static void P6(int n) {
for (int i = 1; i <= n/2; i++)
for ( int j = 1; j <= n/4; j++)
for (int k = 1; k <= n/8; k++)
Procedure();
}

关于java - 时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36041585/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com