算法第四版中命题证明的～符号是什么意思？

问题描述

问 题

算法第四版中命题证明的～符号是什么意思？

例如书中的顺序查找算法中有句话是:向一个空表插入N个不同的键需要～N^2/2次比较。

解决方案

例中 向一个空表插入N个不同的键需要～N^2/2次比较，可以理解为【平均情况下，约】。

由于算法存在最好情况和最坏情况下的时间复杂度（如冒泡最好情况下复杂度其实是 O(1)，而快排最坏情况下其实是 O(N^2) 复杂度），因此书中讨论时一般针对平均意义上的时间复杂度，这时用 ~ 符号是很合理的。

这篇关于算法第四版中命题证明的～符号是什么意思？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！