ToB企服应用市场:ToB评测及商务社交产业平台

标题: 算法学习-1 算法复杂度 [打印本页]

作者: 杀鸡焉用牛刀 时间: 2022-11-18 16:35
标题: 算法学习-1 算法复杂度
一算法复杂度

算法复杂度分为时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。
算法的复杂性体运行该算法时的计算机所需资源的多少，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。

二时间复杂度

2.1 关于时间复杂度

一个算法花费的时间与算法中语句的执行次数成正比例，算法中语句执行次数越多，它花费时间就越多。一个算法中的语句执行次数称为语句时间频度。记为T(n)。

假设算法的问题规模为n，算法中操作单元的数量用函数 f(n) 来表示，当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，
即随着数据规模n的增大，算法执行时间的增长率和 f(n) 的增长率相同，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))。
则称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度(Time complexity)。

时间复杂度用大O符号(big O)表述，不包括f(n)函数的低阶项和首项系数。
不同的数据规模n可能造成算法的运行时间不同，因此通常使用算法的最坏情况来估计时间复杂度。
2.2 常数操作

常数时间的操作:一个操作如果和样本的数据量没有关系，每次都是固定时间内完成操作，叫做常数操作。
常数时间的操作是指算法代码中的指令都是固定时间的操作，指令是和数据量没有关系，比如加、减、乘、除、模、位运算，或数组的寻址。
2.3 常数时间

若对于一个算法，T(n)的上界与输入n的大小无关，则称其具有常数时间，记作O(1)时间。例如访问数组中的单个元素，是常数因为访问它只需要一条指令。
但是，找到无序数组中的最小元素则不是，因为这需要遍历所有元素来找出最小值。这是一项线性时间的操作，也称O(n)时间。
[code]int i = 1;int j = 2;i = j++;j = j

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)