算法第四版中命题证明的～符号是什么意思？
算法第四版中命题证明的～符号是什么意思？
例如书中的顺序查找算法中有句话是:向一个空表插入N个不同的键需要～N^2/2次比较。
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
算法第四版中命题证明的～符号是什么意思？
例如书中的顺序查找算法中有句话是:向一个空表插入N个不同的键需要～N^2/2次比较。
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（2）
例中
向一个空表插入N个不同的键需要～N^2/2次比较，可以理解为【平均情况下，约】。由于算法存在最好情况和最坏情况下的时间复杂度（如冒泡最好情况下复杂度其实是
O(1)，而快排最坏情况下其实是O(N^2)复杂度），因此书中讨论时一般针对平均意义上的时间复杂度，这时用~符号是很合理的。这个符号粗略理解是“大约”，但也可以理解成表示更严格意义上的“等阶无穷大”：
$$f(n) \sim g(n):\quad \lim_{n \to \infty} \frac{f(n)}{g(n)}=1$$