算法与数据结构学习笔记(1)

学了4章才想起来做笔记。。。orz

1、无序数组

运算复杂度:

插入:O(1)

删除:O(N)

查找:O(N)

2、有序数组

运算复杂度:

插入:O(N)

删除:O(N)

查找:O(N)(线性搜索),O(log N)(二分搜索)

3、大O表示法(Big O notation,是这样译没错吧囧)

复杂度排序:O(1) < O(log N) < O(N) < O(N log N) < O(N2)

4、二分搜索

运算复杂度:O(log N)

5、简单排序算法

  • 冒泡排序
  • 选择排序
  • 插入排序

运算复杂度:均为O(N2)

空间复杂度:O(1)

效率比较:冒泡 < 选择 < 插入

6、栈、队列

特性:

栈:后入先出(LIFO)

队列:先入先出(FIFO)

 

运算复杂度:插入和删除均为O(1)

7、优先队列

运算复杂度(数组实现):

插入:O(N)(线性搜索),O(log N)(二分搜索)

删除:O(1)

8、逆波兰表达式

Leave a Reply

Your email address will not be published. Required fields are marked *