Big O - 用值创建哈希表 - 时间复杂度
Big O - Creating Hashtable with values - Timecomplexity
我和我的同学们一直在争论这个重要的符号是什么：
在平均和最坏情况下通过迭代插入（元素数量在开始时已知）创建具有值的哈希表。
插入 1 个元素的平均复杂度为 O(1)，因此在空哈希表中插入 n 个元素应该为 O(n)。
插入 1 个元素的最坏情况是 O(n)。
在空哈希表 O(n^2) 或 O(n) 中插入 n 个元素也是如此，为什么？
最坏的情况是每次插入都会导致冲突。冲突成本取决于散列 table 实现。最简单的实现通常是属于同一哈希单元的所有元素的链表。因此插入 n 个元素将花费 1+2+3+..+n 个时间单位。这是等差级数的和，它等于 n(n+1)/2=O(n2)。这个结果可以通过使用更高级的数据结构来处理冲突来改善。例如，对于 AVL 树，插入成本是 O(logn)，即对于 n 个元素，它将是 O(log1+log2+...+logn)=O(log(n!))，这明显优于 O (n2).
我和我的同学们一直在争论这个重要的符号是什么： 在平均和最坏情况下通过迭代插入（元素数量在开始时已知）创建具有值的哈希表。
插入 1 个元素的平均复杂度为 O(1)，因此在空哈希表中插入 n 个元素应该为 O(n)。
插入 1 个元素的最坏情况是 O(n)。 在空哈希表 O(n^2) 或 O(n) 中插入 n 个元素也是如此，为什么？
最坏的情况是每次插入都会导致冲突。冲突成本取决于散列 table 实现。最简单的实现通常是属于同一哈希单元的所有元素的链表。因此插入 n 个元素将花费 1+2+3+..+n 个时间单位。这是等差级数的和，它等于 n(n+1)/2=O(n2)。这个结果可以通过使用更高级的数据结构来处理冲突来改善。例如，对于 AVL 树，插入成本是 O(logn)，即对于 n 个元素，它将是 O(log1+log2+...+logn)=O(log(n!))，这明显优于 O (n2).