常见算法复杂度

• 复杂度

  • 排序

    • 冒泡、直选、直插 n^2 – 对每个元素找位置、两个for循环嵌套
    • 快排、堆、希尔、归并 nlogn – 二分思想(树)
    • 计数 n+max – 先遍历放到max长度数组，再遍历数组取数
    • 基数 n*位数 – 每位都来来一遍分配
    • 不稳定算法： “快希选堆”（快牺牲稳定性）

  • 查找

    • 分块、二分、二叉排序查找 logn
    • 顺序查找 n
    • 哈希 O(1)

  • 遍历

    • 树遍历：时间复杂度为O(n)，同样空间复杂度也为O(n)，n为结点数。
    • 图遍历： 邻接表O(V+E) 邻接矩阵O(V^2)

  • 红黑

    • 插入、删除、查找的最坏时间复杂度都为 O(logn)。

  • b树

    • 平衡二叉树没能充分利用磁盘预读功能
      B树是为了充分利用磁盘预读功能来而创建的一种数据结构
      专门做索引而发明

  • b+

    • 查找，(m/2) * log(m)n

  • b b+区别

    • 叶子才有数据->减少磁盘io
    • 利于范围查询

本文作者： yuqing wang
本文链接： https://satyrswang.github.io/2021/04/05/常见算法复杂度/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

赏

thanks for tips

支付宝

微信