2011-04-06T03:59:33+08:00 Typecho http://blog.gregwym.info/feed/atom/tag/runtime/ http://blog.gregwym.info/cs-240-fu-xi-zong-jie-zhi-yi--asymptotic-analysis.html 2011-04-06T03:59:33+08:00 2011-04-06T03:59:33+08:00 咳嗽di小鱼 http://blog.gregwym.info

Runtime的符号

• Big-O 表示当c和n0在达到一定大小以后, runtime小于等于某一数级[g(x)]
• Little-O (与Big-O对应) 表示当c和n0为任意值时, runtime一定小于某一数级[g(x)]
• Ω 表示当c和n0达到一定大小以后, runtime大于等于某一数级[g(x)]
• ω (与Ω对应) 表示c和n0为任意值时, runtime一定大于某一数级[g(x)]
• Θ 为同时满足Big-O和Ω

常见的Runtime数级

• Logarithmic (log n)
• Linear (n)
• Linearithmic (n log n)
• Quadratic (n^2)
• Cubic (n^3)
• Exponential (2^n)

更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/

]]>