当前位置:   article > 正文

数据结构1

数据结构1

1.内存用数据结构管理数据,外存(硬盘)用数据库(也称文件)管理数据

2.内存特点:快/小(8G)/带电储存

外存特点:慢/大(500G)/不带电存储

3.顺序表与单链表相比:

前者优点:

(1).下标随机访问(想访问那个就访问哪个)

(2).cpu高速缓存命中率比较高

缺点:(1).前面部分插入删除效率低下

(2).扩容(效率损失)(空间浪费)

后者优点:(1).任意位置插入删除效率都高

(2).按需申请空间,不会浪费

缺点:

(1).不能支持下标随机访问

(2).cpu高速缓存命中率比较低

3.计算机的局部性原理:

计算机在加载某一个数据时,会顺便加载该数据地址往后通常是几十个字节的数据

4.注意画图和思考

5.时间复杂度主要衡量一个算法的运行快慢,空间复杂度主要衡量一个算法运行所需要的额外空间

但现在我们很少考虑到空间复杂度

6.算法的时间复杂度是一个函数(数学里的函数),算法中的基本操作的执行次数,为算法的时间复杂度

例子:

  1. void Func1(int N)
  2. {
  3. int count = 0;
  4. for (int i = 0; i < N; ++i)
  5. {
  6. for (int j = 0; j < N; ++j)
  7. {
  8. count++;
  9. }
  10. }
  11. for (int k = 0; k < 2 * N; ++k)
  12. {
  13. ++count;
  14. }
  15. int n = 10;
  16. while (n--)
  17. {
  18. ++count;
  19. }
  20. }

上述代码的时间复杂度是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.看那个空间复杂度时要注意好整体的算法的逻辑思想

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/154406?site
推荐阅读
相关标签
  

闽ICP备14008679号