Chinese, Simplified subtitles

← 03-25 测试次数,解答

Get Embed Code
3 Languages

Showing Revision 2 created 06/24/2014 by Fran Ontanaya.

  1. 现在来公布答案。
  2. 一个个地解释。
  3. 如果所有的测试都失败了,这确实是个有趣的情况。
  4. 其实不太可能发生的,这里还是假设真发生了吧。
  5. 嗯,那我们最初是把输入分成两个子集,
  6. 第一个子集的删除操作不能通过测试,我们就递归地处理这个子集的子集,N还是=2。
  7. 在这个极端的情况下,我们不停地重复上面的过程,不停地将集合分成两个子集,
  8. 再分成两个,继续分成两个子集,一直分下去,分到不能分为止。
  9. 这就是Kernighan和Pike所描述的二分查找方法,
  10. 是个指数级复杂度的方法。
  11. 下一项:总会存在删除后引起失败的那么一个子集(对半分,一半一半)。
  12. 这也是一样的,除了我们可能会出现像前一半删去后通过了的情况。
  13. 但它的复杂度,也还是指数级的,
  14. 输入长度的指数,所以,还好啦,
  15. delta调试真是很高效的哦!
  16. 实际上,delta调试时,你可以把输入的字符串
  17. 分成两半,哪怕其中一半会通不过测试,但它的表现仍然和二分查找很相似的。
  18. 如果提高了颗粒度,
  19. 它的测试次数就不可能这么少了,
  20. 但其实也不太可能真的这么一个接一个地全删掉来测试。
  21. 它还是挺接近二分查找的高效性的,
  22. 只是,当它一个一个删掉时,会更彻底而全面。
  23. 如果所有的测试都通过了,那delta调试就不是指数的了,
  24. 测试的次数更可能是线性的。
  25. 最后的永不--不对,因为在这两个情况下,
  26. 测试的次数确实是指数级的。
  27. 答案就是这个了。