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的数组,遍历寻找元素x,有n+1中情况,0---n-1位置以及不存在,则有n+1中情况,平均时间复杂度即每种情况平均花费的时间
    其平均时间复杂度为 $$\frac{1+2+…+n+n}{n+1}=\frac{n(n+3)}{2(n+1)}$$,可以简化看作O(n)
    将上述加入概率,假设元素存在为 1/2,元素在任意位置存在为1/n,可以得知每个位置出现的可能性为1/2n,则期望复杂度为$$1\times\frac{1}{2n}+2\times\frac{1}{2n}+…+n\times\frac{1}{2n}+n1\times\frac{1}{2}=\frac{3n+1}{4}$$ ,该值便是加权平均时间复杂度

  • 均摊时间复杂度

    例子
    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;
    }

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

线性表

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

数组

  • 插入操作

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

    插入操作
    1
    2
    3
    4
    5
    void insert(T e,int index) {
    array[count-1] = array[index];
    array[index] = e;
    count++;
    }
  • 删除操作
    可以采取标记删除,当数组容量不够时再进行删除并扩容

链表

单向链表

  • 查询操作
    一般来说都是O(n)复杂度
  • 删除操作
    删除本身来说需要找到指定位置p的前驱,改变p.pre.next = p.next,因此需要执行find操作O(n)找到x.next = p 和p才能完成删除
  • 插入操作
    插入操作需要找到插入位置的节点O(n)

循环链表

该链表用来解决尤瑟夫问题

双向链表

  • 删除操作
    由于持有前驱,因此当找到节点p便可以进行删除
  • 插入操作
    同上
  • 有序双向链表查询操作
    若双向链表有序,可以记录上次查询过的节点,通过此次值和记录节点大小,决定向前还是向后找,可以提高效率
文章作者: fancylight
文章链接: https://www.fancylight.top/2020/07/15/%E7%AE%97%E6%B3%95/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 博客
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论