我们应该什么时候使用软-O，软-欧米茄，软-Theta？
我们应该什么时候使用软-O，软-欧米茄，软-Theta？
提问于 2021-02-10 02:11:46
我对算法领域很陌生，并多次遇到软符号。我不明白软符号的用法。根据维基百科，
‘本质上是大O表示法，忽略了对数因素，因为其他一些超对数函数的增长率效应表明大型输入参数的增长率爆炸，这对于预测糟糕的运行时性能比对数增长因子所造成的更精细的点效应更重要。’https://en.wikipedia.org/wiki/Big_O_notation#Extensions_to_the_Bachmann%E2%80%93Landau_notations
从定义上看，我不太明白软O的用法。有人能给我举个例子吗?我们必须用软O代替大O。非常感谢。
回答 1
Stack Overflow用户
回答已采纳
发布于 2021-02-10 02:57:11
对于不同的精度级别，使用不同的表示法。例如，你可以说
- Mergesort最多使用n⌈lg n⌉比较
- Mergesort使用O(n log )比较
- Mergesort使用
- (N)比较
第一个是挑剔但精确的。第三种是不精确的，但足以将其与插入排序( is (N)和Θ(N 2))进行比较。
使用赋值来抑制单个日志是有点愚蠢的，但是您也可以编写类似log 2 n√(log n) ( log N)= get (1)之类的东西，甚至可以将其扩展到1/ε项用于近似方案，在一个复杂的算法中，这些因素很难跟踪。
不过，你从来不用使用软-O符号。你也不用用大O符号。您可以像Knuth和引用特定实现的MMIX处理器的指令计数一样。只是方便而已。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/66129982
复制相关文章
相似问题
腾讯云开发者
