数据结构公式汇总35知识点

链表

1. 单链表节点个数：n

2. 单链表第 i 个节点：p[i]

3. 单链表尾部插入时间复杂度：O(1)

栈

4. 栈顶元素：栈顶

5. 栈底元素：栈底

6. 进栈时间复杂度：O(1)

队列

7. 队头元素：队头

8. 队尾元素：队尾

9. 入队时间复杂度：O(1)

数组

10. 数组长度：n

11. 数组第 i 个元素：a[i]

12. 数组查找时间复杂度：O(n)

树

13. 树中结点个数：n

14. 树的层数：h

15. 树的度：d

16. 满二叉树结点个数：2^h - 1

17. 完全二叉树结点个数：大于或等于 2^(h-1) - 1

18. 二叉搜索树中查找时间复杂度：O(h)

19. 二叉搜索树中插入时间复杂度：O(h)

图

20. 图中结点个数：n

21. 图中边数：m

22. 图的度：d

23. 有向图中出度：outdeg

24. 有向图中入度：indeg

25. 加权图中权值：w

26. 无向图中最小生成树克鲁斯卡尔算法：O(mlogn)

27. 无向图中最小生成树普里姆算法：O(n^2)

哈希表

28. 哈希表大小：m

29. 哈希表中元素个数：n

30. 哈希表查找时间复杂度：O(1)

优先队列

31. 优先队列中元素个数：n

32. 优先队列中最大/小元素：top

33. 优先队列插入时间复杂度：O(logn)

并查集

34. 并查集大小：n

35. 并查集查找时间复杂度：O(1)