某储备粮的“学习笔记”

by 咳嗽di小鱼

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/