大话数据结构–1.基础知识+2.算法

image

 

2.算法:

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每个指令表现为一个或多个操作。

特性:输入、输出、有穷性、确定性、可行性。

 

2.9.1.算法时间复杂度:

语句的执行次数 T(n)是关于问题规模 n 的函数,进而分析 T(n)的数量级。算法的时间复杂度,也就是算法的时间量度。记作:T(n)= O(f(n)) 。它标识随问题规模 n 的增大,算法执行时间的增长率和 f(n) 的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中 f(n) 是文艺规模 n 的某个函数。

 

2.9.2 推导大O阶方法

1.用常数1取代运行时间中的所有加法常数。

2.在修改后的运行次数函数中,只保留最高阶项。

3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。

得到的结果就是大 O 阶。

事实上,并不这么简单。

 

2.12 算法的空间复杂度

S(n) = O(f(n))

n为问题规模,f(n)为语句关于n所占存储空间的函数。

原文地址:https://www.cnblogs.com/tangge/p/5380590.html