白嫖算法设计与分析

因为这学期选了不少其他限选课,再加上这门课听不少人说考试挺鬼畜的(全考算法证明题),老师挂科率也高(高达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)的上方

发表评论