算法基础
什么是算法
algorithm,最早来自数学领域的概念
衡量算法好坏的重要标准有两个:
时间复杂度
我们使用程序执行次数来代表程序运行时间
T(n),程序基本操作执行次数的函数(通过这个函数可以算出来程序执行多少次数),n是问题的规模
有了T(n),我们是不是就能比较程序运行时间了呢?
并非如此,确定的函数有诸多不变,我们使用的是渐进时间复杂度,说白了就是简化后的T(n),当n趋向于无穷的时候,次数更高的对结果起决定性的作用,我们就用高次项作为渐进时间复杂度
渐进时间复杂度:
如果有f(n),当n趋向于无穷的时候,T(n)/f(n)的值是一个非零的常数,也就是说T(n) f(n)是同等数量级的,记作T(n)=O(f(n)),称为O(f(n)),O为算法的渐进时间复杂度,简称时间复杂度,因为渐进时间复杂度用O表示,所以也被称为大O表示法
推导时间复杂度的原则
如果运行的时间是常数级,则用常数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表示法。表示的是执行算法的空间成本
在运行一段程序的时候,我们不仅是在执行各种指令,同时也会根据需要,存储临时的中间数据
空间复杂度的计算
常量空间:算法的存储空间是确定的,不变的,比如就定义了一个变量,空间复杂度记为O(1)
线性空间:分配的空间是一个线性的集合(比如列表),并且集合的大小和输入的规模n成正比,空间复杂度记为O(n)
二维空间:分配的是个二维列表集合,并且长度和宽度都是和n成正比,那就是O(n^2)
递归空间:虽然递归代码中并没有直接显式地声明变量或者集合,但是计算机在执行的时候,会专门分配一块内存,用来存储“函数调用栈“
每调用一次函数就执行一次入栈操作,把调用的函数和参数信息压入栈中
递归n次,也就是调用函数n次,栈的深度也就是n
当函数返回的时候,执行出栈操作,把调用的函数和参数信息从栈中弹出,一一出栈
执行递归需要的和递归的深度成正比
也就是说纯粹的递归操作的空间复杂度也是线性的,O(n)
什么是数据结构
数据结构,data structure,数据的组织、管理和存储的格式,其目的是高效地访问和修改数据
线性结构
数组,链表、栈、队列、哈希表
树
二叉树、二叉堆
图
多对多的关联关系
more...