已知查找表中有 400 个元素,查找元素概率相同。采用分块查找法且均匀分块。 若采用顺序查找法确定元素所在块,且块内也采用顺序查找法,为效率最高, 每块包含元素应为()
A. 8 B. 10 C. 20 D. 25
根号400=20
分块查找的效率取决于块间查找和块内...
用户登录可进行刷题及查看答案
分块查找的效率取决于块间查找和块内查找的时间复杂度之和。假设将查找表均匀分为 \( m \) 块,每块包含 \( n \) 个元素,则 \( m \times n = 400 \),即 \( m = \frac{400}{n} \)。
#### 时间复杂度分析: 1. **块间查找**:采用顺序查找确定元素所在块,平均查找长度为 \( \frac{m+1}{2} \)。 2. **块内查找**:块内同样采用顺序查找,平均查找长度为 \( \frac{n+1}{2} \)。
**总平均查找长度(ASL)**为两者之和: \[ ASL = \frac{m+1}{2} + \frac{n+1}{2} = \frac{\frac{400}{n} + 1}{2} + \frac{n+1}{2} = \frac{200}{n} + \frac{n}{2} + 1 \]
#### 求极值确定最优 \( n \): 为使 \( ASL \) 最小,对 \( ASL \) 关于 \( n \) 求导并令导数为零: \[ \frac{d(ASL)}{dn} = -\frac{200}{n^2} + \frac{1}{2} = 0 \] 解得: \[ n^2 = 400 \quad \Rightarrow \quad n = 20 \]
#### 验证选项: - 当 \( n = 20 \) 时,\( m = 20 \),代入 \( ASL \) 得: \[ ASL = \frac{20+1}{2} + \frac{20+1}{2} = 21 \] - 对比其他选项(如 \( n=10 \) 时 \( ASL=25.5 \),\( n=25 \) 时 \( ASL=21.7 \)),\( n=20 \) 时总平均查找长度最小,效率最高。
**答案:C. 20**
登录后提交答案