算法 分类

提示

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

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

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 分钟

堆排序

堆

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

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

概率分析和随机化算法

雇佣问题

hire_assistant(n)
  best = 0        // candidate 0 is a least-qualified dummy candidate
  for i = 1 to n
    interview candidate i
    if candidate i is better than candidate best
      best = i
      hire candidate i

被子2024年8月27日大约 6 分钟

分治

矩阵相乘

matrix_multiply(A,B,C,n)
  for i = 1 to n
    for j = 1 to n
      for k = 1 to n
        C[i][j] = C[i][j] + A[i][k] * B[k][j]

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

渐进复杂度

O 定义

公式

\mathcal{O}(g(n)) = \{f(n) : 0 \le f(n) \le cg(n) \; \forall \; n \ge n_0\}

被子2024年8月23日大约 1 分钟

基础排序

插入排序

insertion_sort(A,n)
  for i = 2 to n
    key = A[i]
    // Insert A[i] into the sorted subarray A[1:i-1].
    j = i - 1
    while j > 0 and A[j] > key
      A[j + 1] = A[j]
      j = j - 1
    A[j + 1] = key

被子2024年8月22日大约 1 分钟

算法导论

被子小于 1 分钟

快速排序

堆

雇佣问题

矩阵相乘

O 定义

插入排序