我对算法有一个与语言无关的问题.
这来自我读过的(可能是简单的)编程挑战.问题是,我太愚蠢而无法弄清楚,并且好奇地说它在困扰着我.
目标是通过交换列表中数字的位置来将整数列表按升序排序.每次交换两个数字时,都必须将它们的总和添加到运行总计中.挑战在于生成具有最小可能运行总量的排序列表.例子:
3 2 1 - 4 1 8 9 7 6 - 41 8 4 5 3 2 7 - 34
虽然如果你愿意,你可以自由地给出答案,如果你宁愿在正确的方向上提供"暗示"(如果可能的话),我宁愿这样做.
只读前两段你只是想要一个提示.有一个有效的解决方案(除非我当然犯了错误).首先对列表进行排序.现在我们可以将原始列表编写为不相交周期的产品列表.
例如,5,3,4,2,1有两个循环,(5,1)和(3,4,2).这个循环可以被认为是从3,4开始,3是3点,2是4点,4是3.点.最终目标是1,2,3,4,5或(1)(2)(3)(4)(5),五个不相交的循环.
如果我们从不同的周期切换两个元素,比如1和3,那么我们得到:5,1,4,2,3和循环符号(1,5,3,4,2).这两个循环连接成一个循环,这与我们想要做的相反.
如果我们从同一个循环中切换两个元素,比如3和4,那么我们得到:循环符号(5,1)(2,4)(3)中的5,4,3,2,1.一个循环分成两个较小的循环.这使我们更接近长度为1的所有循环的目标.请注意,在同一循环中任何两个元素的切换都会将循环分成两个循环.
如果我们能够找出用于切换一个周期的最佳算法,我们可以将其应用于所有周期并获得整个排序的最佳算法.一种算法是采用循环中的最小元素并将其与其所处的位置进行切换.因此,对于(3,4,2),我们将使用4切换2.这使得我们得到一个长度为1的循环(元素刚刚切换到正确的位置)和一个比以前小的一个循环.然后我们可以再次应用该规则.该算法将最小元素周期长度切换-1次,每隔一个元素切换一次.
要将长度为n的周期转换为长度为1的周期,需要进行n-1次操作.每个元素必须至少操作一次(考虑每个要排序的元素,必须将其移动到正确的位置).我提出的算法对每个元素进行一次操作,所有算法都必须这样做,然后每个其他操作都在最小元素上完成.没有算法可以做得更好.
该算法需要O(n log n)来排序然后O(n)来混乱循环.求解一个周期需要O(周期长度),所有周期的总长度为n,因此周期操作的成本为O(n).最终运行时间为O(n log n).
京公网安备 11010802040832号 | 京ICP备19059560号-6 