哈希表复杂度分析
来源：14-7 哈希表更复杂的动态空间处理方法
Pro养成记
2019-05-09
在视频2：08秒的PPT上写的是，元素从N增加到upperTol * N, 地址空间倍增。
可我们在编程的时候写的是upperTol * M, 不知道是不是我哪里没搞清楚。
写回答
1回答
-
liuyubobobo
2019-05-09
在复杂度分析中，通常，N是一个代指。
比如，我们说数组中删除一个元素，复杂度是O(n)的，这里的核心意思是，这是一个线性复杂度的操作。但具体这个n在程序里是什么？对于数组来说，这个n可能表示的是数组中元素的数量，即size。当然，你用O(size)，也没有问题。
在这里同理，其实，无论是PPT中的N，还是程序中的M，都是在表示哈希表的容量：）
所以，关键，是要明确复杂度分析符号中，每个变量的语义。具体用什么符号表示，可以不纠结：）
继续加油！：）
00
相似问题
哈希表 复杂度问题
回答 1
线段树空间复杂度问题
回答 1