logo头像

待到风起时,扬帆济沧海

数据结构算法总结

本文于408天之前发表,文中内容可能已经过时。

常用数据结构

image

数据结构分类

分类

数据结构比较

数据结构比较

O符号

  1. O(1):最低的复杂度,无论数据量大小,耗时都不变,都可以在一次计算后获得。哈希算法就是典型的O(1)
  2. O(n):线性,n表示数据的量,当量增大,耗时也增大,常见有遍历算法
  3. O(n²):平方,表示耗时是n的平方倍,当看到循环嵌循环的时候,基本上这个算法就是平方级的,如:冒泡排序等
  4. O(log n):对数,通常ax=n,那么数x叫做以a为底n的对数,也就是x=logan,这里是a通常是2,如:数量增大8倍,耗时只增加了3倍,二分查找就是对数级的算法,每次剔除一半
  5. O(n log n):线性对数,就是n乘以log n,按照上面说的数据增大8倍,耗时就是8*3=24倍,归并排序就是线性对数级的算法
    image

数据结构选择

image

评论系统未开启,无法评论!