恋上数据结构与算法(1-3)

06/13 11:33
阅读数 1.6K

 

 

不加密,高清,无水印

 

https://ke.qq.com/course/385223
腾讯课堂-小码哥教育-MJ恋上数据结构与算法-第一季-1666元

https://ke.qq.com/course/421398
腾讯课堂-小码哥教育-MJ恋上数据结构与算法-第二季-1666元

https://ke.qq.com/course/473705
腾讯课堂-小码哥教育-MJ恋上数据结构与算法-第三季-889元

百度网盘:
链接: https://pan.baidu.com/s/1rG6VFJ4uhZMSXit0Jw043Q 密码: qogr

如果失效加微信itit11223344

 

目录
  • 什么是算法
  • 算法好坏的评判标准
  • 实例讲解时间复杂度
  • 斐波那契数算法剖析
  • 算法的优化方向
一 什么是算法

引用百度百科对算法的解释 算法

算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度时间复杂度来衡量。

  • 例子
// 计算a和b的和
- (int)plus:(int)a b:(int)b { return a + b; } // 计算 1+2+3+...+n 的和 - (int)sum:(int)n { int result = 0; for (int i = 1; i<= n; i++) { result += i; } return result; } 

总结:算法是用于解决特定问题的一系列的执行步骤,使用不同算法,解决同一个问题,效率可能相差非常大。

二 如何评判一个算法的好坏
  • 求 1+2+3+...+n 的和
// 计算 1+2+3+...+n 的和
- (int)sum:(int)n { int result = 0; for (int i = 1; i<= n; i++) { result += i; } return result; } // 计算 1+2+3+...+n 的和 - (int)sum1:(int)n { return (1 + n) * n / 2; } 
2.1 事后统计法

比较不同算法对同一组输入的执行处理时间

上述方案有明显的缺点

  • 1.执行时间严重依赖硬件以及运行时各种不确定的环境因素
  • 2.必须编写相应的测试代码
  • 3.测试事件的选择比较难保证公正性
2.2 时间复杂度+空间复杂度

一般从正确性可读性健壮性(对不合理输入的反应能力和处理能力)等维度来评估算法的优劣。

在满足这些条件的前提下,再比较时间复杂度和空间复杂度

  • 时间复杂度(time complexity):估算程序指令的执行次数(执行时间)
  • 空间复杂度(space complexity):估算所需占用的存储空间
2.3 大O表示法

一般用大O表示法来描述复杂度,它表示的是数据规模n对应的复杂度

忽略常数,系数,低阶

  • 0 >> O(1)
  • 2n + 3 >> O(n)
  • n2 + 2n + 6 >> O(n2)
  • 4n3 + 3n2 + 22n + 100 >> O(n3)

对数阶一般省略底数

因为 log2 n = log2 9 * log9 n,所以

  • log2 n,log9 n统称为 logn

注意:大O表示法仅仅表示一种粗略的分析模型,是一种估算,能帮助我们短时间内了解一个算法的执行效率。

2.4 常见的复杂度
执行次数 复杂度 非正式术语
12 O(1) 常数阶
2n + 3 O(n) 线性阶
4n2 + 2n + 6 O(n2) 平方阶
4log2 n + 25 O(logn) 对数阶
3n + 2nlog3 n + 15 O(nlogn) nlogn阶
4n3 + 3n2 + 22n + 100 O(n3) 立方阶
2n O(2n) 指数阶

复杂度比较:

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n)

可以借助函数生成工具对比复杂度的大小
函数图像绘制工具

2.5 复杂度图形比较
  • 数据规模较小时
 
image.png
  • 数据规模较大时
 
image.png
2.6 实例讲解时间复杂度
  • test1 时间复杂度 O(1)
- (void)test1:(int)n { if (n > 10) { NSLog(@"n > 10"); } else if (n > 5) { // 2 NSLog(@"n > 5"); } else { NSLog(@"n <= 5"); } for (int i = 0; i < 4; i++) { NSLog(@"test1"); } } 
  • test2 时间复杂度 O(n)
- (void)test2:(int)n { // 1 + 3n (指令执行条数) // O(n) for (int i = 0; i < n; i++) { NSLog(@"test"); } } 
  • test3 时间复杂度 O(n^2)
- (void)test3:(int)n { // 1 + 2n + n * (1 + 3n) (指令执行条数) // 1 + 2n + n + 3n^2 // 3n^2 + 3n + 1 // O(n^2) for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { NSLog(@"test"); } } } 
  • test4 时间复杂度 O(n)
- (void)test4:(int)n { // 1 + 2n + n * (1 + 45) (指令执行条数) // 1 + 2n + 46n // 48n + 1 // O(n) for (int i = 0; i < n; i++) { for (int j = 0; j < 15; j++) { NSLog(@"test"); } } } 
  • test5 时间复杂度 O(logn)
- (void)test5:(int)n { // 执行次数 = log2(n) // O(logn) while ((n = n / 2) > 0) { NSLog(@"test"); } } 
  • test6 时间复杂度 O(logn)
- (void)test6:(int)n { // log5(n) // O(logn) while ((n = n / 5) > 0) { NSLog(@"test"); } } 
  • test7 时间复杂度 O(nlogn)
- (void)test7:(int)n { // 1 + 2*log2(n) + log2(n) * (1 + 3n) // 1 + 3*log2(n) + 3 * nlog2(n) // O(nlogn) for (int i = 1; i < n; i = i * 2) { // 1 + 3n for (int j = 0; j < n; j++) { NSLog(@"test"); } } } 
2.6.2 多个数据规模的情况
- (void)test8:(int)n k:(int)k { for (int i = 0; i < n; i++) { NSLog(@"test8 %d",i); } for (int i = 0; i < k; i++) { NSLog(@"test8 %d",i); } } 

时间复杂度为 O(n + k)

2.7 求第n个斐波那契数(fibonacci number)

摘自百度百科的解释 斐波那契数

斐波那契数,亦称之为斐波那契数列(意大利语: Successione di Fibonacci),又称黄金分割数列、费波那西数列、费波拿契数、费氏数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,斐波那契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=Fn-1+Fn-2(n>=2,n∈N*),用文字来说,就是斐波那契数列由 0 和 1 开始,之后的斐波那契数列系数就由之前的两数相加。

2.7.1 算法一
// 递归
- (int)fib1:(int)n { if (n <= 1) { return n; } // Fn = Fn-1 + Fn-2(n >= 2,n∈N*) return [self fib1:n - 1] + [self fib1:n - 2]; } 
2.7.2 算法二
// 直接求值
- (int)fib2:(int)n { if (n <= 1) { return n; } int first = 0; int second = 0; // Fn = Fn-1 + Fn-2 for (int i = 1; i < n; i++) { second += first; first = second - first; } return second; } 
  • TimeTool.m
/// 计算执行完 block 所需花费时间
+ (void)calculateTimeWithTitle:(NSString *)title operationBlock:(void(^)(void))operationBlock { NSDateFormatter *formatter = [[NSDateFormatter alloc] init]; [formatter setDateFormat:@"YYYY-MM-dd HH:mm:ss:mmm"]; NSDate *startDate = [NSDate date]; NSString *currentTimeString = [formatter stringFromDate:startDate]; NSLog(@"%@ start, time = %@",title,currentTimeString); if (operationBlock) { operationBlock(); } NSDate *endDate = [NSDate date]; currentTimeString = [formatter stringFromDate:endDate]; NSLog(@"%@ end, time = %@",title,currentTimeString); NSLog(@"%@ 耗时:%f second",title,[endDate timeIntervalSince1970] - [startDate timeIntervalSince1970]); } 

比较两个算法的时间

- (void)viewDidLoad { [super viewDidLoad]; int n = 35; // fib1 [TimeTool calculateTimeWithTitle:@"fib1" operationBlock:^{ [self fib1:n]; }]; // fib2 [TimeTool calculateTimeWithTitle:@"fib2" operationBlock:^{ [self fib2:n]; }]; } 

n = 35时

 
image.png

n = 44时

 
image.png

经过大量测试,发现当 n < 35的时候,两个算法的执行时间相差不大,但是随着n的增加,相差时间越来越明显了。

2.7.3 两个算法的时间复杂度分析

fib1函数的时间复杂度分析

 
image.png

fib2函数的时间复杂度分析

循环n次,所以时间复杂度为O(n)

三 算法的优化方向
  • 用尽量少的存储空间
  • 用尽量少的执行步骤(执行时间)
  • 根据情况,可以空间换时间或时间换空间
四 扩展

一个用于学习算法的网站

 

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部