时空复杂度（时间复杂度/空间复杂度）O(1)、O(n)、O(n^2)、O(log n)、O(n log n) 是什么意思
阅读目录
- 阐述
- O(1)解析
- O(n)解析
- O() 的写法为：O(n^2)
- O(log n)解析
- O(n log n)解析
阐述
这些都是算法时空复杂度的表示。
不仅仅用于表示时间复杂度，也用于表示空间复杂度。
O 后面的括号中有一个函数，指明某个算法的耗时/耗空间与数据增长量之间的关系。
其中的 n 代表输入数据的量。
O(1)解析
O(1)就是最低的时空复杂度了，也就是耗时 / 耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时 / 耗空间都不变。
哈希算法就是典型的 O(1) 时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话），冲突的话很麻烦的，指向的 value 会做二次 hash 到另外一快存储区域。
通俗易懂的例子
什么是O(1)呢，就比如你是一个酒店的管理员，你负责管理酒店的钥匙，你很聪明，你把酒店的100把钥匙放在了100个格子里面存着，并且把格子从1~100进行了编号，有一天有客人来了，酒店老板说，给我拿10号房间的钥匙给我，你迅速从10
Bertha 。
末蓝、
我会带着你远行
朱雀
忘是亡心i
还没有评论，来说两句吧...