算法基础

什么是算法

algorithm，最早来自数学领域的概念

衡量算法好坏的重要标准有两个：

• 时间复杂度

  我们使用程序执行次数来代表程序运行时间

  1. T(n)，程序基本操作执行次数的函数（通过这个函数可以算出来程序执行多少次数）,n是问题的规模

  2. 有了T(n)，我们是不是就能比较程序运行时间了呢？

     并非如此，确定的函数有诸多不变，我们使用的是渐进时间复杂度，说白了就是简化后的T(n)，当n趋向于无穷的时候，次数更高的对结果起决定性的作用，我们就用高次项作为渐进时间复杂度

  3. 渐进时间复杂度：

     如果有f(n)，当n趋向于无穷的时候，T(n)/f(n)的值是一个非零的常数，也就是说T(n) f(n)是同等数量级的，记作T(n)=O(f(n))，称为O(f(n))，O为算法的渐进时间复杂度，简称时间复杂度，因为渐进时间复杂度用O表示，所以也被称为大O表示法

  4. 推导时间复杂度的原则

     • 如果运行的时间是常数级，则用常数1来表示

     • 只保留时间函数中的最高阶项

     • 如果最高阶项存在，则省去最高阶项前面的系数

     举例：

     （1）T(n) = 3n

     T(n) = O(n)

     （2）T(n) = 5logn

     T(n) = O(logn)

     （3）T(n) = 5

     T(n) = O(1)

     （4）T(n) = 5n^2

     T(n) = O(n^2)

• 空间复杂度

  空间复杂度，采用了和时间复杂度类似的大O表示法。表示的是执行算法的空间成本

  在运行一段程序的时候，我们不仅是在执行各种指令，同时也会根据需要，存储临时的中间数据

  1. 空间复杂度的计算

     • 常量空间：算法的存储空间是确定的，不变的，比如就定义了一个变量，空间复杂度记为O(1)

     • 线性空间：分配的空间是一个线性的集合（比如列表），并且集合的大小和输入的规模n成正比，空间复杂度记为O(n)

     • 二维空间：分配的是个二维列表集合，并且长度和宽度都是和n成正比，那就是O(n^2)

     • 递归空间：虽然递归代码中并没有直接显式地声明变量或者集合，但是计算机在执行的时候，会专门分配一块内存，用来存储“函数调用栈“

       每调用一次函数就执行一次入栈操作，把调用的函数和参数信息压入栈中

       递归n次，也就是调用函数n次，栈的深度也就是n

       当函数返回的时候，执行出栈操作，把调用的函数和参数信息从栈中弹出，一一出栈

       执行递归需要的和递归的深度成正比

       也就是说纯粹的递归操作的空间复杂度也是线性的，O(n)

什么是数据结构

数据结构，data structure，数据的组织、管理和存储的格式，其目的是高效地访问和修改数据

1. 线性结构

   数组，链表、栈、队列、哈希表

2. 树

   二叉树、二叉堆

3. 图

   多对多的关联关系

4. more...