Chinese, Simplified subtitles

← 列表排序续

Get Embed Code
2 Languages

Showing Revision 2 created 05/23/2013 by Lian7.

  1. 回到第一单元,当我们讨论工作复杂性内的步骤时,我们说过
  2. 我们想找到算法,具有和串行算法一样的工作复杂性
  3. 但具有更小的步复杂性。
  4. 在这里归约是个很好的例子,或者扫描。
  5. 但是如果我们说我们做不到,有时候我们愿意
  6. 接受更多的工作,如果让我们用更少的步数。
  7. 而这正是我们这里要做的。但是如何做呢?
  8. 这不是凭直觉,或至少这不适合大多数人,
  9. 当我学习这个资料时,它一定不适合我。
  10. 希尔斯和斯提尔首先表示了怀疑,他们能否改善二次工作量,
  11. 但接着得出结论 —— 我引用他们的论文 ——从本质上我们忽略了
  12. 用多个处理器同时处理问题的能力。
  13. 在较高水平,这是我们要做的。
  14. 在每个节点上,我们开始知道相距1个跃点的节点。这是下一个指针,蓝色的。
  15. 所以在下一次迭代,我们可以访问我们下一个指针的下一个指针,得到距离2 个跃点。
  16. 然后,在下一次迭代,我们可以到距离 3个跃点,以此类推。
  17. 这就是我说直截了当的方法时,想要在这里展示的。
  18. 随着我们增加迭代次数,我们也增加了相距的跃点数。
  19. 但是,这是一种错误的思考方式。
  20. 如果我们只是按这种方式去做,我们会重复很多沿着链的节点在做的工作,
  21. 我们会有二次复杂度的工作。
  22. 相反,在第一次迭代后,我们的每个节点知道相距2个跃点的节点。
  23. 比如说我们对这个节点感兴趣,我们知道我们指向这里的节点 x 。
  24. 好的,通常情况下我们要做的是,我们取这里的红色指针,
  25. 然后把我们的红色指针变成红色指针加上蓝色指针。
  26. 所以,我们会从已知相距 2个 跃点变为已知相距3个跃点的节点。
  27. 但你看,x 也知道相距2 个跃点的节点。
  28. 所以,我知道相距2个跃点的节点,x 知道相距2个跃点的节点。
  29. 所以,在第二次迭代,我们可以利用 x 在第一次迭代已经做过的工作
  30. 来得到一个指针,它现在是相距 4 个跃点。
  31. 所以我们可以用红色,然后红色在这里设置新的红色指针,变成朋友的朋友。
  32. 现在我们要有一个指针指向相距4个跃点的节点,
  33. 这个节点也有一个指针指向相距4个跃点的节点。
  34. 那么下一次迭代将会有一个相距 8 个跃点的指针,以此类推。
  35. 所以,现在不是按照 1,2,3,4,我们现在要按照1、 2、 4、 8。
  36. 所以对于N次迭代,以N的函数表示 ,这需要多少步?