面闭 —— 数据结构
知识点
时间复杂度
通常使用最差的时间复杂度来衡量一个算法的好坏。
常数时间 O(1) 代表这个操作和数据量没有关系,是一个固定时间的操作,比如说四则运算。
对于一个算法来说,可能会计算出操作次数为 aN + 1,N 代表数据量。那么该算法的时间复杂度就是 O(N)。因为在计算时间复杂度的时候,数据量通常是非常大的,这时候低阶项和常数项可以忽略不计。
当出现两个算法都是 O(N) 的时间复杂度,那么对比两个算法的好坏就要通过低阶项和常数项了。
栈
栈是一个线性结构。
栈的特点是只能在某一端添加或删除数据,遵循先进后出的原则。
1 | class Stack { |
队列
队列是一个线性结构。
队列的特点是某一端添加数据,在另一端删除数据,遵循先进先出的原则。
单链队列
1 | class Queue { |
因为单链队列在出队操作的时候需要 O(n) 的时间复杂度,所以引入了循环队列。循环队列的出队操作平均是 O(1) 的时间复杂度。
数组越界
比如数组定义时有十个元素,那么a[0] – a[9] 分别对应相应的元素,在程序中如果使用了a[10]那么就超出了原来的数组定义的范围,这就是数组下标越界。
循环队列?
链表
面试题
相关资料
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.