目录
什么是算法
算法是用于解决特定问题的一系列的执行步骤
比如：
//计算a跟b的和
-(int)plustWithA:(int)a b:(int)b{
return a+b;
}
//计算 1+2+3+...n的和
-(int)sumWithN:(int)n{
int result = 0;
for (int i=1; i<=n; i++) {
result += i;
}
return result;
}
//计算 1+2+3+...n的和
-(int)subWithN2:(int)n{
return (1+n)*n/2;
}
斐波那契数列
一、斐波那契数列计算
使用不同算法，解决同一个问题，效率可能相差很大
比如：求第n个斐波那契数（fibonacci number）
0 1 1 2 3 5 8 13 …
//使用递归方式求斐波那契数列
-(int)fibWithN:(int)n{
if (n<=1) return n;
return [self fibWithN:n-2]+[self fibWithN:n-1];
}
//使用循环方式求斐波那契数列
-(int)fibWithN2:(int)n{
if(n<=1) return n;
int first = 0;
int second = 1;
for (int i= 2; i<=n; i++) {
int sum = first + second;
first = second;
second = sum;
}
return second;
}
//11:06:55.733516+0800 LCClientDemo[35082:4053920] result = 0
//11:07:00.744194+0800 LCClientDemo[35082:4053920] result = 102334155
//用时：5秒
for (int i=0; i<=40; i++) {
int result = [self fibWithN:i];
NSLog(@"result = %d",result);
}
NSLog(@"-------------");
//11:07:00.744311+0800 LCClientDemo[35082:4053920] result2 = 0
//11:07:00.745024+0800 LCClientDemo[35082:4053920] result2 = 102334155
//用时：0秒
for (int i=0; i<=40; i++) {
int result = [self fibWithN2:i];
NSLog(@"result2 = %d",result);
}
二、如何评判一个算法的好坏？
1、如果单从执行效率上进行评估，可能会想到这么一种方案
比较不同算法对同一组输入的执行处理时间
这种方案也叫做：事后统计法
2、上述方案有比较明显的缺点
执行时间严重依赖硬件以及运行时各种不确定的环境因素
必须编写相应的测算代码
测试数据的选择比较难保证公正性
3、一般从以下维度来评估算法的优劣
正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）
时间复杂度（time complexity）：估算程序指令的执行次数（执行时间）
空间复杂度（space complexity）：估算所需占用的存储空间
大O表示法
一、一般用大O表示法来描述复杂度
它表示的是数据规模n对应的复杂度。忽略常数、系数、低阶
9 » O(1)
2n + 3 » O(n)
n2 + 2n + 6 » O(n2)
4n3 + 3n2 + 22n + 100 » O(n3)
写法上，n3 等价于 n^3
注意：大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率
对数阶的细节
对数阶一般省略底数
log2n = log2^9 ∗ log9^n
所以 log2^n 、log9^n 统称为logn
二、复杂度从优到劣排序
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
可以借助函数生成工具对比复杂度的大小 https://zh.numberempire.com/graphingcalculator.php
三、分析下列函数的复杂度
-(void)test1:(int)n{
// 汇编指令
// 1
if (n > 10) {
NSLog(@"n>10");
} else if (n > 5) { // 2
NSLog(@"n>5");
} else {
NSLog(@"n <= 5");
}
// 1 + 4 + 4 + 4
for (int i = 0; i < 4; i++) {
NSLog(@"test");
}
// 14
// 时间复杂度：O(1)
// O(1)
}
-(void)test2:(int)n{
// 1 + 3n
for (int i = 0; i < n; i++) {
NSLog(@"test");
}
//时间复杂度：O(n)
}
-(void)test3:(int)n{
// 1 + 2n + n * (1 + 3n)
// 1 + 2n + n + 3n^2
// 3n^2 + 3n + 1
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
NSLog(@"test");
}
}
//时间复杂度：O(n^2)
}
-(void)test4:(int)n{
// 1 + 2n + n * (1 + 45)
// 1 + 2n + 46n
// 48n + 1
for (int i = 0; i < n; i++) {
for (int j = 0; j < 15; j++) {
NSLog(@"test");
}
}
//时间复杂度：O(n)
}
-(void)test5:(int)n{
// 8 = 2^3
// 16 = 2^4
// 3 = log2(8)
// 4 = log2(16)
// 执行次数 = log2(n)
// O(logn)
while ((n = n / 2) > 0) {
NSLog(@"test");
}
//时间复杂度：O(logn)
}
-(void)test6:(int)n{
// log5(n)
// O(logn)
while ((n = n / 5) > 0) {
NSLog(@"test");
}
//时间复杂度：O(logn)
}
-(void)test7:(int)n{
// 1 + 2*log2(n) + log2(n) * (1 + 3n)
// 1 + 3*log2(n) + 2 * nlog2(n)
// O(nlogn)
for (int i = 1; i < n; i = i * 2) {
// 1 + 3n
for (int j = 0; j < n; j++) {
NSLog(@"test");
}
}
//时间复杂度：O(nlogn)
}
//多个数据规模的情况
-(void)test8:(int)n k:(int)k{
// 1 + 3n+1+3k
// O(n+k)
for (int i = 1; i < n; i = i * 2) {
NSLog(@"test");
}
for (int i = 1; i < k; i++) {
NSLog(@"test");
}
//时间复杂度：O(n+k)
}
//时间与空间复杂度
-(void)test10:(int)n{
// 4
int a = 10;
int b = 20;
int c = a + b;
int* array = malloc(n*sizeof(int));
//1 + 3n
for (int i = 0; i < (int)sizeof(array)/sizeof(int); i++) {
NSLog(@"%d",array[i]+c);
}
free(array);
//4+1+3n
//时间复杂度：O(n)
//变量a+b+c+array需开辟空间:1+1+1+n
//空间复杂度：O(n)
}
fib函数复杂度分析
一、递归方式计算斐波那契数列的时间复杂度：
二、循环方式计算斐波那契数列的时间复杂度：
一个n次的for循环可知其时间复杂度为O(n)
三、他们的差别有多大？
如果有一台1GHz的普通计算机，运算速度10^9次每秒（n为64）
O(n)大约耗时6.4 ∗ 10^(−8)秒
O(2^n)大约耗时584.94年
有时候算法之间的差距，往往比硬件方面的差距还要大
四、Something interesting
我是一个斐波那契程序员
因为我每天都在改昨天和前天的bug
算法的优化方向
1、用尽量少的存储空间
2、用尽量少的执行步骤（执行时间）
3、根据情况，可以空间换时间或者时间换空间
行者常至，为者常成！