赞
踩
1.内存用数据结构管理数据,外存(硬盘)用数据库(也称文件)管理数据
2.内存特点:快/小(8G)/带电储存
外存特点:慢/大(500G)/不带电存储
3.顺序表与单链表相比:
前者优点:
(1).下标随机访问(想访问那个就访问哪个)
(2).cpu高速缓存命中率比较高
缺点:(1).前面部分插入删除效率低下
(2).扩容(效率损失)(空间浪费)
后者优点:(1).任意位置插入删除效率都高
(2).按需申请空间,不会浪费
缺点:
(1).不能支持下标随机访问
(2).cpu高速缓存命中率比较低
3.计算机的局部性原理:
计算机在加载某一个数据时,会顺便加载该数据地址往后通常是几十个字节的数据
4.注意画图和思考
5.时间复杂度主要衡量一个算法的运行快慢,空间复杂度主要衡量一个算法运行所需要的额外空间
但现在我们很少考虑到空间复杂度
6.算法的时间复杂度是一个函数(数学里的函数),算法中的基本操作的执行次数,为算法的时间复杂度
例子:
- void Func1(int N)
- {
- int count = 0;
- for (int i = 0; i < N; ++i)
- {
- for (int j = 0; j < N; ++j)
- {
- count++;
- }
- }
-
- for (int k = 0; k < 2 * N; ++k)
- {
- ++count;
-
- }
- int n = 10;
- while (n--)
- {
- ++count;
- }
-
- }
上述代码的时间复杂度是F(N) = N ^ 2 + 2 * N + 10
时间复杂度是带未知数N的函数式
7.大O的渐进表示法(估算),算个大概,算它是属于哪个量级
8.通常取时间复杂度的1项或2项作为它的量级
例;F(N) = N ^ 2 + 2 * N + 10
当N趋于无穷时,F(N)后边那两项几乎可以忽略不计,所以它的档次是O(N ^ 2)
9.常见的档次:
O(1)
O(N)
O(N ^ 2)
O(N ^ 3)
O(N * logN)
O(logN)
10.O(1)代表常数次
11.推导大O阶方法:
1、用常数1取代运行时间中的所有加法常数。(函数式中只有常数)
2、在修改后的运行次数函数中,只保留最高阶项。
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。
12.算法要考虑最坏情况
13.冒泡排序的时间复杂度是N^2
14.二分查找的时间复杂度是logN
15.logN默认是以二为底N的对数
16.我们要考虑好代码的实现难度,简洁程度,(可读性,可维护性)
17.在复杂度方面,我们一般考虑时间复杂度而不考虑空间复杂度
18.qsort是快速排序,是O(N * logN)
19.看那个空间复杂度时要注意好整体的算法的逻辑思想
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。