百科问答小站 logo
百科问答小站 font logo



一个算法面试题,怎么写? 第1页

  

user avatar   hao-di-fang-bug 网友的相关建议: 
      

这是一个很有趣也很常见的问题,但是很不幸的是,这个问题是NP-hard[1],也就是说除非 否则没有多项式时间算法。

但是我们可以用动态规划设计一个伪多项式的算法[2] ,虽然也没有那么简单。当然,一个带剪枝的搜索算法,应该是很容易实现的,我想这应该也是这道面试题的初衷。

另外这篇review[3] 总结了了很多这类工作安排问题的复杂度和算法,虽然都是些上世纪的研究,但也是很全面和深刻的。

参考

  1. ^Du J, Leung J Y T. Minimizing total tardiness on one machine is NP-hard[J]. Mathematics of operations research, 1990, 15(3): 483-495. https://doi.org/10.1287/moor.15.3.483
  2. ^Lawler E L. A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness[M]//Annals of discrete Mathematics. Elsevier, 1977, 1: 331-342. https://www.sciencedirect.com/science/article/pii/S0167506008707428
  3. ^A Review of Machine Scheduling: Complexity, Algorithms and Approximability https://link.springer.com/chapter/10.1007/978-1-4613-0303-9_25



  

相关话题

  红黑树的实现可以有多精简(各种语言随意)? 
  一个N*N的矩阵,取值为0或1,有什么好的算法判断一行或一列全为1啊? 
  「贪心算法」的算法思路是什么,它存在什么缺陷? 
  掷一枚不均匀的硬币,正面概率为0.7,反面的概率为0.3,如何最高效地获得一个概率为0.5的事件? 
  如何看待王思聪开始第二波抽奖,这轮抽奖结果的性别比是否会发生明显的变化? 
  如何理解计算物理中的元胞链接列表(Cell Linked List)算法? 
  如何找到一个10项的非负整数数列,使该数列的任意不超过3项的和不重复,并使数列的最大项最小,并证明? 
  卡尔曼滤波器是如何运用于多传感器融合的? 
  是否存在一个函数,使得它的逆运算是容易求的,而它的逆运算的逆运算是难求的? 
  中宣部等五部门要求治理算法推荐,不给错误内容提供传播渠道,你认为目前算法推荐存在哪些问题? 

前一个讨论
Linux的ls -l命令输出的第二列的数字代表什么?
下一个讨论
火星风暴有危险吗?





© 2025-05-01 - tinynew.org. All Rights Reserved.
© 2025-05-01 - tinynew.org. 保留所有权利