dgo*_*sen 3 big-o time-complexity
如上定义的陈述"f(x)是O(g(x))"通常写为f(x)= O(g(x)).有些人认为这是对符号的滥用,因为使用等号可能会产生误导,因为它表明这种说法没有对称性.正如de Bruijn所说,O(x)= O(x ^ 2)为真但O(x ^ 2)= O(x)不是
我理解正式定义但不是de Bruin所说的.我试图理解O(x)= O(x ^ 2)或甚至O(x)是O(x ^ 2)的真正含义.
直观地,我会将其读作"具有复杂度x的函数类与具有复杂度x ^ 2的函数类相同".但这没有意义.
在Wikipedia讨论页面没有太大的帮助要么.
直观地,我会将其读作"具有复杂度x的函数类与具有复杂度x ^ 2的函数类相同".但这没有意义.
是的,这就是为什么人们不喜欢等号的符号.
它应该读作"具有复杂度x的函数类包含在具有复杂性x ^ 2的函数类中"或"具有复杂性的线性上界的函数也是具有二次上部复杂性界限的函数"(其中)当然二次约束不是很紧.)
| 归档时间： |
|
| 查看次数： |
545 次 |
| 最近记录： |