哈希表复杂度分析

Question

在视频2：08秒的PPT上写的是，元素从N增加到upperTol * N, 地址空间倍增。

可我们在编程的时候写的是upperTol * M, 不知道是不是我哪里没搞清楚。

Answer 1

liuyubobobo 2019-05-09 15:46:19

在复杂度分析中，通常，N是一个代指。

比如，我们说数组中删除一个元素，复杂度是O(n)的，这里的核心意思是，这是一个线性复杂度的操作。但具体这个n在程序里是什么？对于数组来说，这个n可能表示的是数组中元素的数量，即size。当然，你用O(size)，也没有问题。

在这里同理，其实，无论是PPT中的N，还是程序中的M，都是在表示哈希表的容量：）

所以，关键，是要明确复杂度分析符号中，每个变量的语义。具体用什么符号表示，可以不纠结：）

继续加油！：）