算法之美-入门准备


算法入门准备

学习知识的过程是反复迭代、不断沉淀的过程,我们一起加油

目标:写出达到开源水平的框架

算法和数据结构是什么?

数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组方法”。数据结构和算法是相辅相成的。数据结构是为算法服务的,算法要作用在特定的数据结构之上

(1)常用数据结构

  • 数组、链表、栈、队列、散列表
  • 二叉树、堆、跳表、图、Trie树

(2)常用算法

  • 递归、排序、二分查找、搜索
  • 哈希算法、贪心算法
  • 分治算法、回溯算法
  • 动态规划、字符串匹配算法

思维导图

思维导图

怎么样衡量数据结构和算法?

时间复杂度和空间复杂度

相关参考

复杂度分析

为什么评估算法?

执行效率关乎时间成本、存储空间关乎硬件成本。数据结构和算法本身解决的是“快”和“省”的问题

如何评估算法

事后统计法

通过统计、监控,就能得到算法执行的时间和占用的内存大小,这种统计法有非常大的局限性

  1. 测试结果非常依赖测试环境
  2. 测试结果受数据规模的影响很大

大 O 复杂度表示法

一个不用具体的测试数据来测试,就可以粗略地估计算法的执行效率的方法

例一
int cal(int n) {
    int sum = 0;
    int i = 1;
    for (; i <= n; ++i) {
          sum = sum + i;
    } 
    return sum; 
}

从 CPU 的角度来看,这段代码的每一行都执行着类似的操作:读数据-运算-写数据。
尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样,我们这里假设每行代码执行的时间都一样为 unit_time

  • unit_time
    • 2、3 行
  • n * unit_time
    • 4、5 行
  • 总时间
    • T(n) = (2n+2)*unit_time
    • 即:y = k * x

可以看出所有代码的执行时间 T(n) 与每行代码的执行次数成正比

例二
int cal(int n) {
    int sum = 0; 
    int i = 1; 
    int j = 1; 
    for (; i <= n; ++i) { 
        j = 1; 
        for (; j <= n; ++j) {
            sum = sum + i * j; 
        } 
    } 
}
  • unit_time
    • 2、3、4 行
  • n * unit_time
    • 5、6 行
  • n * n * unit_time
    • 7、8 行
  • 总时间
    • T(n) = (2n^2 +2n + 3)*unit_time
    • 即:y = x^2 + x + k

可以看出所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比

大O时间复杂度上场

我们根据这个规律总结成一个公式:T(n) = O(f(n))

  • T(n): 代码执行的时间
  • n: 表示数据规模的大小
  • f(n): 表示每行代码执行的次数总和
  • O: 表示代码的执行时间 T(n) 与 f(n) 表达式成正比

大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度

当 n 很大时,公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。如果用大 O 表示法表示刚讲的那两段代码的时间复杂度,就可以记为:T(n) = O(n); T(n) = O(n^2)

时间复杂度-百度百科
时间复杂度-维基百科

时间复杂度分析

  • 时间复杂度
    常见的时间复杂度

空间复杂度分析

  • 只关注循环执行次数最多的一段代码
  • 加法法则:总复杂度等于量级最大的那段代码的复杂度
  • 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

几种常见时间复杂度实例分析

  • O(1)
  • O(logn)、O(nlogn)
  • O(m+n)、O(m*n)

四个维度的复杂度分析

例一

分析下面代码的时间复杂度

// n表示数组array的长度
int find(int[] array, int n, int x) 
{ 
    int i = 0;
    int pos = -1; 
    for (; i < n; ++i) 
    { 
        if (array[i] == x) 
            pos = i; 
    } 
    return pos;
}
  • 复杂度是 O(n)

简单优化一下代码

// n表示数组array的长度
int find(int[] array, int n, int x)
{ 
    int i = 0; 
    int pos = -1; 
    for (; i < n; ++i) 
    { 
        if (array[i] == x) 
        { 
            pos = i; 
            break; 
        } 
    }
    return pos;
}
  • 时间复杂度

    • 如果数组中第一个元素正好是要查找的变量 x,那时间复杂度就是 O(1)。
    • 但如果数组中不存在变量 x,那我们就需要把整个数组都遍历一遍,时间复杂度就成了 O(n)。
  • 最好情况时间复杂度

    • 最好情况时间复杂度就是,在最理想的情况下,执行这段代码的时间复杂度
    • 即第一个元素就是要查找的元素
  • 最坏情况时间复杂度

    • 最坏情况时间复杂度就是,在最糟糕的情况下,执行这段代码的时间复杂度
    • 需要把整个数组都遍历一遍
  • 平均情况时间复杂度

    要查找的变量 x 在数组中的位置,有 n+1 种情况:在数组的 0~n-1 位置中和不在数组中。我们把每种情况下,查找需要遍历的元素个数累加起来,然后再除以 n+1,就可以得到需要遍历的元素个数的平均值,即:
    平均情况时间复杂度

    • 以上结论并非如此完全正确,需加上一些概率论的知识

      我们知道,要查找的变量 x,要么在数组里,要么就不在数组里。这两种情况对应的概率统计起来很麻烦。我们假设在数组中与不在数组中的概率都为 1/2。另外,要查找的数据出现在 0~n-1 这 n 个位置的概率也是一样的,为 1/n。所以,根据概率乘法法则,要查找的数据出现在 0~n-1 中任意位置的概率就是 1/(2n)
      平均情况时间复杂度加概率

    • 这个值就是概率论中的加权平均值,也叫作期望值,所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度

    • 加权平均时间复杂度O((3n+1)/4)去系数后仍然是O(n)

例二

// 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;
}

当数组满了之后,也就是代码中的 count == array.length 时,我们用 for 循环遍历数组求和,并清空数组,将求和之后的 sum 值放到数组的第一个位置,然后再将新的数据插入。但如果数组一开始就有空闲空间,则直接将数据插入数组。

  • 最好时间复杂度 O(1)
  • 最坏时间复杂度 O(n)
  • 加权平均复杂度 O(1)
    加权平均复杂度
  • 例子
    • 例一 是find()查询方法
      • 在极端情况下,复杂度才为 O(1)
    • 例二 是insert()插入方法
      • 在大部分情况下,时间复杂度都为 O(1)。
      • O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入,出现的频率是非常有规律的,而且有一定的前后时序关系,一般都是一个 O(n) 插入之后,紧跟着 n-1 个 O(1) 的插入操作,循环往复。
      • 每一次 O(n) 的插入操作,都会跟着 n-1 次 O(1) 的插入操作,所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上,均摊下来,这一组连续的操作的均摊时间复杂度就是 O(1)。
  • 均摊时间复杂度
    • 均摊时间复杂度应用的场景比平均复杂度更加特殊、更加有限
    • 均摊时间复杂度就是一种特殊的平均时间复杂度

例三

// 全局变量,大小为10的数组array,长度len,下标i。
int array[] = new int[10]; 
int len = 10;
int i = 0;
// 往数组中添加一个元素
void add(int element) 
{ 
    if (i >= len) 
    { 
        // 数组空间不够了 
        // 重新申请一个2倍大小的数组空间 
        int new_array[] = new int[len*2]; 
        // 把原来array数组中的数据依次copy到new_array 
        for (int j = 0; j < len; ++j) 
        { 
            new_array[j] = array[j]; 
        } 
        // new_array复制给array,array现在大小就是2倍len了 
        array = new_array; 
        len = 2 * len; 
    }
    // 将element放到下标为i的位置,下标i加一 
    array[i] = element; 
    ++i;
}
  • add()新增函函数
    • 最好时间复杂度是O(1)
    • 最差时间复杂度是O(n)
    • 均摊时间复杂度是O(1)

文章作者: 韩思远
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 韩思远 !
评论
 上一篇
算法前言 算法前言
前言 如何高效的学习数据结构和算法? 期待效果 职业顶尖级别——对算法的理解 一线互联网公司面试 LeetCode 300+的积累 精通一个领域 Chunk it up 切碎知识点 庖丁解牛 脉络连接 Deliberate Prac
2020-08-31
下一篇 
JQuery基础 JQuery基础
JQuery基础 一. jQuery 简介什么是 jQuery jQuery 是一个轻量级, 简洁的 JavaScript 库, 是继 Prototype 之后的一个优秀的 JavaScript 库. jQuery 的理念: Write
2020-08-01
  目录