2020-10-12（算法基础）

算法的基本概念和要素

• 运算
• 查找
• 排序
• 最优决策

数据结构

为了更高效地存储、访问和修改数据，数据结构就产生了。

• 线性结构
  数组、链表（衍生——>栈、队列、哈希表）
• 树
  二叉树、二叉堆等
• 图
  多对多的关联关系
• 其他
  由基础的数据结构变形而来，为了解决某些特定的问题。（跳表、哈希链表、位图）

时间复杂度

基本操作执行次数

受运行环境 输入规模的影响，程序运行的绝对执行时间是无法确定的。

灵魂拷问：你还记得log2(下标)n吗？
对数，以2为底，n的对数，也就是n要除以2多少次才能得到1。

程序执行次数可能与输入规模（n）存在一定的对应关系，如

• T(n) = 3n;
• T(n) = 5logn;
• T(n) = 3;
• T(n) = 3n^2 + 3n;
  这就呈现了一定的对应关系。

那么3n 一定小于 5logn吗？？

渐进时间复杂度

若存在f(n)使得当n无穷大时，T(n)/f(n)的极值为不为0的常数，则该f(n)是T(n)的同数量级函数。

T(n) = O(f(n))。这个O就是时间复杂度。他将相对时间函数T(n)简化为一个数量级（n、n^2、n3）

推导时间复杂度

• 如果运行时间为常数量级，则用1表示；
• 保留时间函数中的最高阶项；
• 如果最高阶存在，则省去前系数。

1、T(n) = 3n ——> T(n) = O(n);
2、T(n) = 5logn ——> T(n) = O(logn);
3、T(n) = 3 ——> T(n) = O(1);
4、T(n) = 3n^2 + 3n ——> T(n) = O(n^2);

如果n足够大，他们的时间大小为
O(1) < O(logn) < O(n) < O(n^2)

空间复杂度

在运算的过程中，我们经常需要一些中间数据来辅助我们更好地进行计算，那这些中间数据用什么数据结构来存储才能提高我们的运算效率呢?

S(n) = O(f(n))
同样的，他也有几种随n增长的趋势变化：

• 当所占空间与输入规模n无关时（只需要固定的存储空间），其空间复杂度记作O(1)；
• 分配的空间为一个线性的集合（数组等），且集合大小与n成正比，则记作O(n)；
• 分配空间为二维空间（二维数组[][]），且长度与宽度都与n成正比，则记作O(n^2)；
• 递归空间，当执行递归时，系统会分配一块空间来存储方法调用栈，存在两个动作"入栈"和"出栈"，当我们每次递归执行函数时，系统都会将函数代码和参数压入栈中，而当函数执行返回操作时，才会出栈。很明显，空间复杂度与递归深度成正比，即O(n)；

两者该如何权衡，还是具体看应用场景的，一般来说，大家对程序执行的时间要求比较苛刻。