常用的排序算法的时间复杂度和空间复杂度
|
排序法
|
最差时间分析
|
平均时间复杂度
|
稳定度
|
空间复杂度
|
|
冒泡排序
|
O(n
2
)
|
O(n
2
)
|
稳定
|
O(1)
|
|
插入排序
|
O(n
2
)
|
O(n
2
)
|
稳定
|
O(1)
|
|
选择排序
|
O(n
2
)
|
O(n
2
)
|
稳定
|
O(1)
|
|
二叉树排序
|
O(n
2
)
|
O(n*log
2
n)
|
不一顶
|
O(n)
|
|
快速排序
|
O(n
2
)
|
O(n*log
2
n)
|
不稳定
|
O(log
2
n)~O(n)
|
|
堆排序
|
O(n*log
2
n)
|
O(n*log
2
n)
|
不稳定
|
O(1)
|
|
希尔排序
|
O
|
O
|
不稳定
|
O(1)
|
查找算法时间复杂度
|
查找
|
平均时间复杂度
|
查找条件
|
算法描述
|
|
顺序查找
|
O(n)
|
无序或有序队列
|
按顺序比较每个元素，直到找到关键字为止
|
|
二分查找（折半查找）
|
O(logn)
|
有序数组
|
查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。 如果在某一步骤数组为空，则代表找不到。
|
|
二叉排序树查找
|
O(logn)
|
二叉排序树
|
在二叉查找树b中查找x的过程为：
1. 若b是空树，则搜索失败
2. 若x等于b的根节点的数据域之值，则查找成功；
3. 若x小于b的根节点的数据域之值，则搜索左子树
4. 查找右子树。
|
|
哈希表法（散列表）
|
O(1)
|
先创建哈希表（散列表）
|
根据键值方式(Key value)进行查找，通过散列函数，定位数据元素。
|
|
分块查找
|
O(logn)
|
无序或有序队列
|
将n个数据元素"按块有序"划分为m块（m ≤ n）。
每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……。然后使用二分查找及顺序查找。
|
&n...
《
算法
赏析》课程介绍
“软件 =
算法
+
数据结构
”，
算法
是软件的灵魂。在信息时代，计算思维是分析复杂工程问题的重要思维方式，计算机则是求解问题的重要工具。本课程以计算机经典问题求解为导向，通用
算法
思维和自动编程流程图培养为目标，引入经典
算法
，精心安排课程的理论教学和编程实践。本课程学习将有助于学员提高计算思维能力及
算法
思维的能力。
本课程主要讲授计算机问题求解的经典
算法
设计方法和
算法
复杂度分析方法，主要内容包括计算机概述、计算机系统的组成、信息化及指标体系、操作系统、程序设计语言、
算法
简介、数的表示及存储、
数据结构
简介及顺序结构和选择结构、循环结构、循环的嵌套、
算法
复杂度分析，枚举
算法
，递归与分治策略，递归与迭代的思想、求最大值最小值、线性
查找
、二分
查找
与冒泡
排序
以及选择与交换
排序
、插入和希尔
排序
。本课程除了强调经典的
算法
理论和模型，亦兼顾编程实践能力。力图使得学员面对复杂问题时，既能“想到”还能“做到”。
培养
算法
思维，掌握枚举
算法
、分治策略、递归与迭代、选择与交换
排序
等经典
算法
模型；
培养实践能力，掌握在存储空间和时间开销受限情况下的程序设计方法；
培养理论思维，掌握复杂问题的
算法
设计与分析方法。
1、
算法
的复杂度
算法
在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个
算法
的好坏，一般是从时间和空间两个维度来衡量的，即
时间复杂度
和
空间复杂度
。
时间复杂度
主要衡量一个
算法
的运行快慢，而
空间复杂度
算法
是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的
算法
，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。
那么我们应该如何去衡量不同
算法
之间的优劣呢？
主要还是从
算法
所占用的「时间」和「空间」两个维度去考量。
时间维度：是指执行当前
算法
所消耗的时间，通
常用
「
时间复杂度
」来描述。
空间维度：是指执行当前
算法
需要占用多少内存空间，通
常用
「
空间复杂度
」来描述。
接下来主要介绍
时间复杂度
和
空间复杂度
的计算方法。
一、
时间复杂度
O
时间复杂度
并不具体表示代码
数据量大：每天会有亿级数据产生，历史累计万亿级数据。
数据同时使用情况：用户量是百万级的，电商特殊抢购场景下，千亿级用户量同时使用。比如，大家抢同一件商品。
信息技术不断发展：CPU一次计算的时间是0.2ns~0.3ns，计算速度相当于每秒几十亿次。
数据结构
的意义在于：合理规划数据，保证在大数据时代，在数据层面保持高速客观的数据操作（就是对数据的增删改查）。
常见的
时间复杂度
时间复杂度
概念：x>1,x足够大的时候，想要达成某个数据操作目的，所需要计算的次数就是
时间复杂度
.
