面试常见问题02 - 算法与数据结构（施工ing）

2019-07-02 本文已影响0人第八天的蝉啊

1. 哈希冲突的解决办法

分离链接法：将发生冲突的元素保存到同一个表中
开放定址法：发生冲突时使用探测函数探测可用的位置
再散列：扩大散列表的规模

2. 排序算法时间和空间复杂度

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
插入排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
希尔排序	$O(nlogn)-O(n^2)$	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定
堆排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	不稳定
归并排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(n)$	稳定
快速排序	$O(nlogn)$	$O(nlogn)$	$O(n^2)$	$O(logn)-O(n)$	不稳定

1. 求二叉树的深度

1. 01背包问题

上一篇下一篇

猜你喜欢

热点阅读