東京大学 新領域創成科学研究科 メディカル情報生命専攻 2019年8月実施 問題7
Author
Description
Let
Operation: choose arbitrary
We denote the largest number in array
(1) Let
(2) When
(3) When
(4) Show an algorithm that computes
(5) Let
(6) Let
设
操作:选择满足
我们将数组
(1) 设
(2) 当
(3) 当
(4) 使用 (2) 和 (3) 展示一个从
(5) 设
(6) 设
Kai
(1)
Given
For
To find
Initial array:
We need to check all possible adjacent swaps under the condition
Swap
Swap
Swap
Swap
All valid permutations for
Therefore, for
For
For
Initial array:
We start with the initial array and apply all valid swaps:
Swap
Swap
Swap
Now explore permutations of
Swap
Now explore permutations of
Swap
Swap
Now explore permutations of
Swap
Now explore permutations of
Similarly, we get:
Thus, the valid permutations for
Therefore, for
(2)
When
Given
Therefore, the number of permutations of
(3)
When
If
(4)
Algorithm to compute
def compute_S(A, W):
if len(A) == 0:
return 1
# O(N)
a_h = max(A)
a_l = min(A)
if a_h + a_l < W:
# O(N)
A_minus_a_l = [x for x in A if x != a_l]
return len(A) * compute_S(A_minus_a_l, W)
# T(N-1)
else:
index_h = A.index(a_h)
left_part = A[:index_h]
right_part = A[index_h+1:]
return compute_S(left_part, W) * compute_S(right_part, W)
# 2*T(N/2)
# Example
A = [4, 1, 10, 3, 2]
W = 11
print(compute_S(A, W)) # Output: 4
W = 12
print(compute_S(A, W)) # Output: 10
(5)
Given that the worst-case scenario involves removing the smallest element each time, the time complexity can be analyzed as follows:
- Initial size:
- Operation: Finding the smallest element (which takes
time) and removing it, reducing the problem size by 1. - Recurrence relation: The total time complexity is the sum of the times taken for each step as we reduce the size of the array from
to 0.
The time complexity can be expressed as:
This is the sum of the first
Therefore, the worst-case time complexity is:
(6)
Assuming that each of the
In the average case, the algorithm will involve both scenarios of removing the smallest element and splitting the array. However, the average number of operations will not always hit the worst-case scenario.
Considering the balanced approach where the split operation happens frequently, the recurrence relation can be described more favorably compared to the worst-case:
Using the Master Theorem for
Thus, the average time complexity is:
Knowledge
组合计数 递归 复杂度分析 主定理
解题技巧和信息
- Recursive Reduction: Understand how reducing a problem by removing an element or splitting the array affects complexity.
- Complexity Analysis: Sum of first
numbers is . - Master Theorem: Useful for solving recurrence relations in divide-and-conquer algorithms.
重点词汇
- worst-case 最坏情况
- average-case 平均情况
- time complexity 时间复杂度
- recurrence relation 递推关系
参考资料
- Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, Chapter 4.