作业: 算法分析 01

2026-09-30 算法分析作业
算法分析CS作业

Problem 1

Let and . Is ? Is ? Prove your answers. You are allowed to use either the definition or techniques described in class.

Proof

均不是. 若, 则存在与, 满足对任意的:

取, 有

矛盾.

若, 则存在与, 满足对任意的:

取, 有

矛盾.

Problem 2

Give an example of a function that is , and prove that it is. Using the definition (or think intuitively).

Reminder. means: for every constant there is an such that for all .

Proof

考虑, 对任意的, 取, 则对任意的, 都有. 因此.

Problem 3

You are told that .

  1. Is it true that ? Argue your answer.

  2. Is it true that ? Argue your answer.

Proof

  1. 取, , 有. 但, , . 即. 因此命题不成立.

  2. 存在与, 使得对所有,

    则有

    即.

Problem 4

  1. Prove that if , then .

  2. If , is it necessarily true that ? Prove your answer.

Proof

  1. 存在与, 满足对任意的,

    因此

  2. . 显然, 但显然.

Problem 5

Find out what is wrong with the following sentence:

Analyze from a mathematical point of view what this statement actually says.

Proof

这句话是无意义的. 只要取, 以上结论永远成立.

Problem 6 (Correctness of Bubblesort)

Bubblesort is a popular but inefficient sorting algorithm. It sorts in place by repeatedly swapping adjacent elements that are out of order.

Algorithm 1: BUBBLESORT

1  for i <- 1 to n - 1 do
2      for j <- n downto i + 1 do
3          if A[j] < A[j - 1] then
4              swap A[j] and A[j - 1]

Let denote the array when BUBBLESORT finishes. To prove that Bubblesort is correct, we must show that it terminates and that

  1. What else must be proved before we can say that Bubblesort really sorts ?

  2. Prove that Bubblesort is correct. (Hint: using the loop-invariant technique covered in class for insertion sort, see also CLRS, Section 2.1 and problem 2-2). Your proof should establish the equation and also the property from part (a).

Proof

  1. 需要证明和元素完全相同.

  2. 先证明

    2      for j <- n downto i + 1 do
    3          if A[j] < A[j - 1] then
    4              swap A[j] and A[j - 1]

    执行完毕后会将中的最小元素排到最左侧, 且元素与初始状态相同. 考虑取循环不变式: 每次for循环内语句开始前, 是的最小元素, 且仍然由原先的元素组成.

    • 初始化: 当时, 只有一个元素, 显然正确.
    • 保持: 若循环不变式对于成立, 算法将比较与. 并将其更小的元素交换到前面. 因此执行后是的最小元素, 因为最小元素不可能在以后. 同时, 由于过程中只进行了交换, 元素的组成不变.
    • 终止: 循环结束时, 执行完比较后, 是中的最小元素.

    再证明

    1  for i <- 1 to n - 1 do
    2      for j <- n downto i + 1 do
    3          if A[j] < A[j - 1] then
    4              swap A[j] and A[j - 1]

    执行完毕后满足且元素与初始数组相同. 考虑取循环不变式: 每次最外层for循环内语句执行前, 都有, 且仍然由原来的元素组成.

    • 初始化: 当时, 是空数组, 每个位置上的元素均与初始状态相同, 显然正确
    • 保持: 若循环不变式对于成立. 内层循环会将的最小元素移动到, 因此满足了. 同时, 过程中所有改变元素位置的操作都是交换, 因此不会改变初始元素.
    • 终止: 循环结束后, 等价于的语句开始前, 因此满足且元素与初始数组相同.

    同时, 该算法的循环至多执行次, 因此该算法可以在有限步终止. 该算法正确.