Lesson 04

作业评论

时间复杂度Time Complexity

均摊分析Amortized Analysis

背景

ArrayList::add(1)

时间复杂度 不扩容时 $O(1)$ ， 扩容时 $O(n)$

是什么

连续进行 n 次操作，计算平均下来的时间复杂度

计算方法

计算每一次的开销

n 次 的单位时间 求和

再除 n

线性数据结构

栈Stack

操作

push 加元素

pop 删元素

peek / top 查看顶元素

size 几个元素

要求

先 push 的 最后 pop

举例

麦当劳的外卖纸袋

手机应用

实现

Array / Link

队列Queue

操作

enqueue 加元素

dequeue 删元素

要求

先 enqueue 的 先 dequeue

举例

叫号系统

实现

Array / Link

作业