avatar

算法

算法入门

时间复杂度

大O时间复杂度

  • 常见复杂度

    |复杂度|术语|
    |—-|—-|
    |O(1)|常数阶|
    |O(log(n))|对数阶|
    |O(n)|线性阶|
    |O(nlog(n))|对数阶|
    |O(2^n)|指数阶|
    |O(n!)|阶乘阶|
    |O(n^k)|k次方阶|

其中将O(2^n)O(n!)称为非多项式量级,该类问题就是NP问题
图像如下,来源bigocheatsheet

  • 相关问题
    • 对数阶以2为底
      1
      任意对数都可以转化为以2为底,log3 n=log32  * log2 n,可以看作O(Clogn)
    • O(m+n)、O(m*n)
      加法原则:当多个复杂度堆叠时,若可以判断不同部分的数量级时,可使用大的替代整体,否则相加计算
      乘法原则: T1(m)*T2(n) = O(f(m) * f(n))。
      

      其他时间复杂度

  • 最好,最坏时间复杂度
    如二叉树的最坏时间复杂度为(O(n))即链表

  • 平均时间复杂度
    如在长度为n的数组,遍历寻找元素:
    其平均时间复杂度为 ,可以简化看作O(n)
    将上述加入概率,假设元素存在为,元素在任意位置存在为,则期望复杂度为,该值便是平均时间复杂度

  • 均摊时间复杂度

    例子
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20

    // array表示一个长度为n的数组
    // 代码中的array.length就等于n
    int[] array = new int[n];
    int count = 0;

    void insert(int val) {
    if (count == array.length) {
    int sum = 0;
    for (int i = 0; i < array.length; ++i) {
    sum = sum + array[i];
    }
    array[0] = sum;
    count = 1;
    }

    array[count] = val;
    ++count;
    }

    计算其时间平均时间复杂度为
    最好时间复杂度为:
    最坏时间复杂度为:
    在该例子中可以将最后出现的O(n)操作均摊到每一次的O(1)操作上,那么可以理解均摊时间复杂度就是特殊的平均时间复杂度

    线性表

    简单来说数组,队列,栈,链表都是线性表,可以集中来分析插入,删除操作的复杂度,以及其方式

    数组

  • 插入操作

插入操作最差时间复杂度: O(n),平均时间复杂度
当插入操作的目标数组并非要保持有序,可将插入位置元素挪到队尾,然后插入,则时间复杂可视为O(1)

插入操作
1
2
3
4
void insert(T e,int index) {
array[count-1] = array[index];
array[index] = e;
}

  • 删除操作
    可以采取标记删除,当数组容量不够时再进行删除并扩容

    链表

文章作者: fancylight
文章链接: https://www.fancylight.top/2020/07/15/%E7%AE%97%E6%B3%95/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 博客
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论