算法第四版中命题证明的~符号是什么意思?
本文介绍了算法第四版中命题证明的~符号是什么意思?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
问 题
算法第四版中命题证明的~符号是什么意思?
例如书中的顺序查找算法中有句话是:向一个空表插入N个不同的键需要~N^2/2次比较。
解决方案
例中 向一个空表插入N个不同的键需要~N^2/2次比较
,可以理解为【平均情况下,约】。
由于算法存在最好情况和最坏情况下的时间复杂度(如冒泡最好情况下复杂度其实是 O(1)
,而快排最坏情况下其实是 O(N^2)
复杂度),因此书中讨论时一般针对平均意义上的时间复杂度,这时用 ~
符号是很合理的。
这篇关于算法第四版中命题证明的~符号是什么意思?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文