文章 | 博客演示

h: U \rightarrow \{0,1,...,m - 1\}

被子2025年4月2日大约 4 分钟

中位数和顺序统计

选择问题

输入：n 个不同的数字和一个整数 i，1 ≤ i ≤ n
输出：第 i 大的元素 x

最小和最大

MINIMUM(A,n)
  min = A[1]
  for i = 2 to n
    if min > A[i]
        min = A[i]
  return min

被子2025年3月8日大约 2 分钟

线性时间排序

提示

基于比较的排序算法在最坏情况下至少需要比较 $\Omega(nlgn)$ 次

被子2024年12月20日大约 2 分钟

蒙特卡洛积分

蒙特卡洛估计

给定 1D 积分 $\int_a^b f(x) dx$ ，我们随机采样一组独立的均匀随机变量 $X_i \in [a,b]$ ，蒙特卡洛估计值等于

被子2024年11月29日大约 7 分钟

快速排序

quicksort(A,p,r)
  if p < r
    // Partition the subarray around the pivot, which ends up in A[q].
    q = partition(A,p,r)
    quick_sort(A,p,q-1)
    quick_sort(A,q+1,r)

被子2024年11月24日大约 3 分钟

纹理

纹理放大

双线性插值采样

纹理缩小

Mipmapping

被子2024年10月31日大约 1 分钟

着色基础

概览

光源

方向光

点光源

聚光灯

被子2024年10月27日大约 1 分钟

光栅化

光栅化线段 (Bresenhan Line Algorithm)

规则

diamond-exit rule

对于每一个像素点，如果线段和该像素点内的钻石区域相交并且从该区域内穿出即（exit），则着色该像素点；因此如果线段终点在像素钻石区域内，但没有穿出的话，那么也不着色该像素点，这样保证当有两段连续的线段连接在一起的时候，连接处的像素点只会绘制一次。

被子2024年10月11日大约 3 分钟

坐标变换

线性代数基础

任意 n 阶段矩阵 M 可以看成由 n 个列向量 c₁ c₂ ... c_n 组成：

M = \begin{bmatrix} \mathbf{c_1} & \mathbf{c_2} & ... & \mathbf{c_n} \\ \end{bmatrix}

被子2024年9月7日大约 9 分钟

堆排序

堆

PARENT(i)
  return i/2
LEFT(i)
  return 2i
RIGHT(i)
  return 2i+1

被子2024年9月2日大约 2 分钟

哈希表