datastructure

Data Structure

n个数值选出最大m个数(3<m<n)的最小算法复杂度是

  1. 最简单的方法:将 n 个数排序,排序后的前k个数就是最大的k个数,这种算法的复杂度是O(nlogn)
  2. O(n) 的方法:利用快排的 patition 思想,基于数组的第k个数来调整,将比第k个数小的都位于数组的左边,比第k个数大的都调整到数组的右边,这样调整后,位于数组右边的k个数最大的k个数(这k个数不一定是排好序的)
  3. O(nlogk) 的方法:先创建一个大小为k的最小堆,接下来我们每次从输入的n个整数中读入一个数,如果这个数比最小堆的堆顶元素还要大,那么替换这个最小堆的堆顶并调整。

由权值分别为1、12、13、4、8的叶子节点生成一颗哈夫曼树,它的带权路径长度为()

二叉树先序、后序遍历

  • 先序遍历
1
2
3
4
5
6
7

根 ↓
↓ -----------
A B D C E G F H I
---


  • 中序
1
2
3
4
5
6


B D A G E C H F I
--- -----------
↑ ↑
左 右
  • 后序
1
2
3
4
5
6
7


-----------
D B G E H I F C A
--- ↑
↑ 根

Binary Heap 调整

Quick Sort 调整

1
12,15,1,18,2,35,30,11

12 为基准记录的一趟快速排序结束后的结果为:

快速排序里的挖坑填补法:以 12 为标准值,从右开始找比12的值,首先是 11,把 11 放在 12 的那个位置,把12放在11的位置,再从左找比12的值15,把 15 放在 12 的新位置(原11的位置)之后变成 11,12,1,18,2,35,30,15. 在新的一轮开始,从右开始找12 小的数是2,把2放在12的位置,12放在2的位置,在从左找比12大的数18,把18放在12的新位置上(原2的位置)变成11,2,1,12,18,35,30,15.

多项式 P(X)=a+bx+cx^2+dx^3 ,对于任意 x ,计算 P(X) 中最少需要用到乘法操作的次数是多少?

一般地, 一元 n 次多项式 的求值需要经过 2n-1 次乘法和 n 次加法,而 秦九韶算法 只需要 n 次乘法和 n 次加法 。
题目中P(X)是3次多项式,所以3次乘法。

推荐文章