算法的时间复杂度和空间复杂度
算法 About 1,139 words算法的时间复杂度和空间复杂度
算法的时间复杂度
计算程序执行时间
事后统计:打印程序的耗时时间,依赖于计算机硬件等因素,需在同一台计算机相同状态运行程序才准确。
事前估算:分析算法的时间复杂度来判断算法的优劣。
时间频度
算法中语句的执行次数。
常见时间复杂度
时间复杂度依次从小到大。
常数阶 O(1)
只要没有循环,不管多少行代码都是O(1)
。
func ConstantTime(i, j int) int {
var a,b int
if i%2 == 0 {
a = i+j
}
if j%2 == 1 {
b = i+j
}
return a+b
}
对数阶 O(log2n)
func LogarithmicTime(n int) {
i := 1
for i < n {
i = i * 2
}
}
线性阶 O(n)
func LinearTime(n int) {
// 几百万行代码
for i := 0; i < n; i++ {
// 几百万行代码
}
// 几百万行代码
}
线性对数阶 O(n log n)
func LinearithmicTime(m, n int) {
for i := 0; i < m; i++ {
j := 1
for j < n {
j = j * 2
}
}
}
平方阶 O(n2)
func QuadraticTime(n int) {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
fmt.Printf("%d\t%d", i, j)
}
fmt.Println()
}
}
立方阶 O(n3)
三层n
循环。
K 次方阶 O(nK)
K
层n
循环。
指数阶 O(2n)
平均时间复杂度
所有可能的输入以等概率的时间出现的情况。
最坏时间复杂度
一般讨论的时间复杂度都是最坏时间复杂度。最坏情况下算法运行时间的边界。
算法的空间复杂度
定义
算法所耗费的存储空间(内存)。
备注
快速排序和归并排序占用较多的存储单元。
Redis
,基数排序,二级缓存,三级缓存,都是属于空间换时间。
参考
Views: 1,258 · Posted: 2021-02-02
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...