数据库结构与算法
1、什么是算法:
计算机解决解决某个问题特定任务的具体实现步骤。
算法是独立解决问题的一种方法和解决思路
2、算法特性:
输入:有0个或者多个参数
输出:至少有一个以上的计算结果,
有穷性:算法在有限的步骤内会自动结束,不会无限循环,并且每一个执行步骤是需要的时间是可接受的
确定性:算法的每一个步骤必须要有确定的含义,不能出现二义性
可行性:算法执行的没一个步骤都是可性的,每一步骤都会在有限的执行次数完成
3、时间复杂度
实现算法的执行时间可以反应出
算法的时间效率称为时间复杂度
可以用这段程序的最终要发挥的基本步骤来描述他的算法优略性,哪这个描述基本运算数量的总和叫做 时间复杂度
总执行时间 = 基本运算数量 * 每一个基本运算时间
4、时间复杂度表达式
eg:
for i in range(0,1000): for ii in range(1000): for iii in range range(1000): if i+ii+iii==12345 and i+ii=100: print(i,ii,ii)
T = 1000 * 1000 * 1000 * 2
T = n * n * n * 2
T(n) = n^3 * 2
T(n) = k*g(n) + c
g(n) = n*3
T(n) = n^3
k:常数
c:系数 可以为 0
n:解决问题的规模
g(n): g(n)是T(n)的渐进函数,也就是g(n)能够表达出T(n)时间复杂度的一个特征【g(n)是T(n)去除旁支末节(常熟项、系数),只留下最主要的特征部分】
T(n):时间复杂度【对于某个问题解决步骤的统一标识】
大O表示法:g(n)就叫做一个时间复杂度T(n) 的大O表示法
5、最坏时间复杂度
最优时间复杂度:算法完成任务最少需要多少基本操作。最乐观的情况,没有参考价值。
最坏时间复杂度:算法完成任务最多需要多少基本操作。提供一种保障,在最坏的情况下也能完成任务 ***
平均时间复杂度:算法完成任务平均需要多少基本操作。对算法的全面评价,反应了算法的性质,但是这种评价并不准确
关注:最坏时间复杂度 --> 最优时间复杂度
6、时间复杂度计算规则:
1) 基本操作,即只有参数项,认为其时间复杂度为 O(1)
2) 顺序结构,时间复杂度按照 加法计算
3) 循环结构,时间复杂度按照 乘法计算
4) 分支机构,时间复杂度去最大值
5) 判断一个算法的效率时,往往只关注操作数量最高次项,其他次要项和参数项目可以忽略不记
6) 没有特殊说明,一般分析的算法的时间复杂度都是指 最坏时间复杂度
7、常见时间复杂度