因为这学期选了不少其他限选课,再加上这门课听不少人说考试挺鬼畜的(全考算法证明题),老师挂科率也高(高达30%+),就算过了得分也不好看(均分75) 所以没选,但毕竟还是挺有用的感觉,所以跟着舍友旁听了。
虽说不用交作业不用考试,但还是开个笔记好好学下……(虽然还是分而治之和图算法占大半篇幅
1.渐进表示法
- 大
\Omicron
表示法
定义:
\Omicron (g(n)) = \{f(n): 存在正数c和n_0,使得当n \ge n_0时0 \le f(n) \le cg(n)恒成立 \}
表示时间复杂度最好的情况,即f(n)总在cg(n)的下方
- 大
\Omega
表示法
定义:
\Omega (g(n)) = {f(n): 存在正数c和n_0,使得当n \ge n_0时0 \le cg(n) \le f(n)恒成立 }
表示时间复杂度最差的情况,即f(n)总在cg(n)的上方