@
bkjzs 我刚刚看了算法,这本书上没有这部分,我又去 YouTube 上看了 MIT 算法导论的公开课,忍受了一个印度口音叨叨半小时,我只弄懂了小 o 和θ,还终于弄明白了为什么在 java 中 variable declaration =2 但我没看到有ω,不知道你看的哪本书,我只有 algorithm 4th 的实体书,没有算法导论的实体,你可以发一份你的书给我看一下。
小 o 就是高数里面的定义,比如 g(n) = (1/2) n^2+( 1/2 ),f(n)=n^2 , g/f=1/2,你可以计作大 O(n^2),而小 o 则一定要是高阶无穷小, f(n)=n^3 就是 g/f=0,计作小 o(n^3),你可以理解为用大 O 的时候 g/f 可以是等于 0 或者等于 C ,但小 o 一定要等于 0,至于θ就是 f 严格等于 g , f(n)等于(1/2) n^2+( 1/2 ),而大 O 只需要 f(n)=n^2 ,你可以计作用θ时候 g/f 一定要等于 1 。
PS :楼主非 CS 专业,编程最近才开始看,不过自认为对自己感兴趣的事情理解能力比较强,如果解释的不对,下面的人一定要告诉我,别误导别人,待会我会更新一下大 O 的文章。