排序算法的时间复杂度

Question

我有两个关于时间复杂性的问题.

1)我似乎还没有掌握大哦或兰道的符号.我知道它用于表示时间复杂性,但为什么我只能说最坏情况下的时间复杂度,比如冒泡排序是n ^ 2而不是O(n ^ 2)？

2)为什么日志会在一段时间内复杂化？例如,为什么以及如何确定shell排序O(nlogn)的最坏情况时间复杂度？

关于这些事情的任何好网站,除了维基百科,将不胜感激.

Answer 1

1. Big-O表示法用于表示您正在谈论渐近行为.如果您只是编写n^2,可能会假设您正在讨论特定程序的实际运行时(即您可以直接从该表达式获得运行时间).但实际上,您的运行时将是一种形式a.n^2 + b.n + c.log(n) + d.Big-O表示法允许您忽略所有低阶项,因为n从无穷大开始,它只是重要的n^2术语.

2. 我不确定shell排序的最坏情况复杂性O(n log n).但是log当某些东西被连续分成两部分时(例如,考虑平衡二叉树的高度),经常会出现这种情况.