|
??在以n描述问题规模的前提下。
??对于以下几种算法：
循环类
一、
while (i * i < n) {
i++;
}
??复杂度
O
(
n
)
O(\sqrt{n})
O(n
?)
二、
while (i < n) {
i *= 2;
}
??复杂度
O
(
l
o
g
2
n
)
O(log_2 n)
O(log2?n)
三、
while (pow(n, m) < n) {
i++;
}
??复杂度
O
(
n
1
m
)
O(n^{\frac{1}{m}})
O(nm1?)
四、
while (i < n) {
i *= m;
}
??复杂度
O
(
l
o
g
m
n
)
O(log_mn)
O(logm?n)
递归类
一、
int func(int n) {
if (n == 0) return 1;
return n * func(n - 1);
}
??复杂度
O
(
n
)
O(n)
O(n)
二、
int func(int n) {
if (n == 0) return 1;
return n * func(n / 2);
}
??复杂度
O
(
n
?
l
o
g
2
n
)
O(n·log_2 n)
O(n?log2?n)
int func(int n) {
if (n == 0) return 1;
return n * func(sqrt(n));
}
??复杂度
O
(
n
?
n
)
O(n·\sqrt{n})
O(n?n
?)
|