SIT221 Data Structures and Algorithms课程辅导

对本文有疑问可以加微信 Tutor_0914联系。也可查看个人辅导网站了解详情：

tutoryou辅导详情

lecture2

概念解释

内排序（In-place）：所有排序操作都在内存中完成 外排序（Out-place）：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
stable:

排序算法理解

这里推荐使用可视化的一些网站：
排序可视化

算法分析

想知道给定一个规模n，花费的理论上的时间。

运行时间是原子操作的数量。

Asymptotic Notations

更关注这个数量级，Consider orders of magnitude.

渐进如何理解

n不同，时间复杂度也不同，我们认为是n趋近于无穷大时，最坏的情况下的复杂度。

几种表示方法分别代表什么含义

视频
大O，最坏情况下，算法的复杂度不会超过大O。
是算法的上界。
小o，

最好情况，最坏情况，加和除以2，就是平均情况。

几道题练习一下

$\sigma$

同阶，又是上界，又是下界。
大O，上界,同阶或者高阶
小o，上界，高阶
大sigma，下界，低阶或者同阶

task2.1