1.算法复杂度

1.1.时间复杂度

算法的执行时间与算法的输入值之间的关系

大O表示法

指算法的最糟糕情况下的运行时间

经常遇到的5种大O运行时间

• ，也叫对数时间，算法代表：二分查找
• ，也叫线性时间，算法代表：简单查找
• ，算法代表：快速排序
• ，算法代表：选择排序
• ，旅行商问题

1.2.空间复杂度

算法的存储空间与输入值之间的关系

1.3.总结

时间和空间只能二选一
面试时：和面试官讲清楚
工作时：时间>空间

2.数据结构

2.1.数组

在连续的内存空间中，存储一组相同类型的元素

元素和索引

访问(access)和搜索(search)

访问：a[1]=>2
搜索：2这个元素

时间复杂度

访问Access：O(1)
搜索Search：O(N)
插入Insert：O(N)
删除Delete：O(N)

特点

适合读，不适合写

推荐练习题

485，283，27

2.2.链表

时间复杂度

访问Access：O(N)
搜索Search：O(N)
插入Insert：O(1)
删除Delete：O(1)

特点

适合写，不适合读

推荐练习题

203，206

2.1和2.2拓展：链表数组

2.3.队列

图解

时间复杂度

访问Access：O(N)
搜索Search：O(N)
插入Insert：O(1)
删除Remove：O(1)

特点

先入先出

单端队列

只有一个口进，一个口出

双端队列

两个口都可以进，两个口都可以出

练习题推荐

933