错题

约 175 个字 预计阅读时间 1 分钟

• When we solve the summation problem via designing the parallel algorithms, we shorten the asymptotic time complexity but take more asymptotic work loads comparing with the sequential algorithms.

  • F:Workload没有增加，处理器数量增加了

• There are inputs that force any on-line bin-packing algorithm to use at least twice the optimal number of bins.

  • ？

• You have 10 identical cores on which you want to schedule some \(n\) jobs. Each job \(j\in\{1,2,\ldots,n\}\) has a processing time \(p_j>0\). If \(S_i\) is the set of jobs assigned to core \(i\), let the load be \(\sum_{j\in S_i}p_j.\) Now, you want to partition the jobs among the cores to minimize the load of the most-loaded core.

  We design a greedy algorithm that picks any unassigned job, and assign it to the core with the least current load.

  What is the approximation ratio of the greedy algorithm? (Choose the smallest bound that applies.)

  A.1.5 B.1 C.2 D. 1.9

  hb哥构造的：