简谈算法复杂度
时间复杂度 和 空间复杂度就是算法存在的意义
1. 算法复杂度分为时间复杂度和空间复杂度
空间复杂度:算法执行需要花费的内存(暂不讨论)
时间复杂度:算法执行需要花费的时间
算法的时间复杂度,用来度量算法的运行时间,记作: T(n) = O(f(n)). 它表示随着输入大小n的增大,算法执行需要的时间都增长速度可以用f(n)来描述。
2. 定理:
2.1常数项对函数的增长速度影响并不大,所以当T(n) = c, c为一个常数的时候,我们说这个算法的时间复杂度为O(1)
void func1() {
int i = 100; //执行一次
int j = 0; //执行一次
j = i; //执行一次
j ++; //执行一次
}该算法一共执行 T(n) = 1 + 1 + 1 + 1 = 4 = O(1);
2.2如果T(n)不等于一个常数项时,直接将常数项省略
void func2() {
int j = 100; //执行一次
int i = 0; //执行一次
for (int i = 0; i <= 2*j; i++) { //执行2j次
int k = 0; //执行2j次
}
}该算法一共执行 T(n) = 1 + 2j + 2j = 4j + 1 = O(j);
2.3因为函数的介数对函数的增长速度的影响是最显著的,所以我们忽略与最高阶相乘的常数
void func1(int n) {
for (int i = 0; i <= n; i++) { //执行n次
for (int j = 0; j <= n; j++) { //执行n^2次
for (int k = 0; k <= n; k++) { //执行n^3次
System.out.println(111);
}
}
}
}该算法一共执行 T(n) = n + n^2 + n^3 = O(n^3);
2.4算法考虑的是最坏情况下程序执行的次数,而非最好情况下程序执行的次数
public void func1() {
char array1[] = {'a','b','c','d','e'}; //执行1次
char array2[] = {'h','i','a','j','k'}; //执行1次
for (int i = 0; i <= array1.length; i++) { //执行array1.length次
for (int j = 0; i <= array2.length; i++) {//执行array2.length次
if (array1[i] == array2[j]) {
return;
}
}
}
}该算法一共执行3次,3位常数 T(n) = O(1);
void func1(char array1[], char array2[]) {
for (int i = 0; i <= array1.length; i++) {
for (int j = 0; i <= array2.length; i++) {
if (array1[i] == array2[j]) {
return;
}
}
}
}该算法一共执行 T(n) = O(array1.length * array2.length);
3. 例题:
例题1:
// 假设 n > i
public void func1(int n) {
int i = 0; //执行一次
while(i < n) {
i += 2;
}
}假设当经过P次以后 i>=n成立,则当
p=1: f(1) = 0 + 2;
p=2: f(2) = f(1) + 2;
p=3: f(3) = f(2) + 2;
…
p=p: f(p) = f(p-1) + 2;等式左右两边相加得:f(1)+f(2)+f(3)+…+f(p) = (0+2)+(f(1)+2)+(f(2)+2)+…+(f(p-1)+2);
左右两边消去相同项得:f(p)=2p.
现有2p=n p=n/2
则该方法的时间复杂度为:O(n/2),根据定理2.2得该方法的时间复杂读为O(n)
例题2:
// 假设 n > i
void func(int n) {
int i = 1; //执行一次
while(i < n) {
i *= 2;
}
}假设当经过P次以后 i>=n成立,则当
p=1: f(1) = 1 * 2;
p=2: f(2) = f(1) * 2;
p=3: f(3) = f(2) * 2;
…
p=p: f(p) = f(p-1) *2;等式左右两边相乘得:f(1)*f(2)*f(3)*…*f(p) = (1*2)*(f(1)*2)*(f(2)*2)*…*(f(p-1)*2);
左右两边消去相同项得:f(p)=2^p
现有2^p=n p=log2n
则该方法的时间复杂度为:O(log2n)
例题3:
void func(int n) {
int i = 0;
while(i * i * i <= n)
i++;
}假设当经过P次以后 iii>n成立,则当p=p: f(p) = (f(p) + (p-1)) ^3;
则一定有:f(p) = f(i+p)^3 + a(f(i+p-1)^2) + b(f(i+p-1)) + c > n
则f(i)^3 +x (f(i)^2) + y(f(i)) + z > n
根据定理2.3得:f(i)^3 > n i = log3n
则该方法的时间复杂度为:O(log3n)
例题4:
// 假设 n > i
void func1(int n) {
int i = 0;
int s = 0;
while(s < n) {
++ i;
s += i;
}
}假设经p次循环后结束,s>=n
则:
f(1) = 1;
f(2) = f (1) + 2;
f(3) = f (2) + 3;
......
f(p) = f(p-1) + p;等式左右两边相加得:f(1)+f(2)+f(3)+…+f(p) = 1+(f(1)+2)+(f(2)+3)+…+(f(p-1)+p);
左右两边消去相同项得:
f(p)=1+2+3…+p;
f(p) = p(1+p)/2(等差数列求和通项公式)则该方法的时间复杂度为:O(log2n)
例题5:
// 假设 n > i
void func(int n) {
if(n <= 1) return 1;
return n * func(n-1);
}
当n = 1 时:
n = 1时, f(1) = 1;
n = 2时, f(2) = 2 * f(1);
n = 3时, f(3) = 3 * f(2);
…
n = n时, f(n) = n * f(n-1);两边相乘得:
f(1) * f(2) * f(3) * … * f(n) = 1 * (2 * f(1)) * (3 * f(2)) * … * (n * f(n-1))
则f(n) = n!
则:O(n) = O(n!) = O(n) (用归纳法可得O(n!) = O(n))4. 算法在编程中的应用:
假设当存在字符集两个数组char array1[]，char array2[]，判断当两个字符集有重复字符时就返回true，否则返回false，其中char array1[]长度为n， char array2[]为n。
普通青年:
public Boolean func1(char array1[], char array2[]) {
for (int i = 0; i <= array1.length; i++) {
for (int j = 0; i <= array2.length; i++) {
if (array1[i] == array2[j]) {
return Boolean.TRUE;
}
}
}
return Boolean.FALSE;
}该算法一共执行 T(n) = O(n^2);
算法青年:
public Boolean fun1(char array1[], char array2[]) {
Map arrayMap = new HashMap<>(array1.length * 2);
for(int i = 0; i < array1.length; i++) {
arrayMap.put(array1[i], i);
}
for(int j = 0; j < array2.length; j++) {
if (arrayMap.containsKey(array2[j])) {
return Boolean.TRUE;
}
}
return Boolean.FALSE;
}查看Map底层源码,根据key找value的时间复杂度为O(1);
该算法一共执行 T(n) = O(n + n) = O(n);
当n越大时,第一种实现方式和第二种实现方式体现出来的差距越大,这就是算法的魅力!
