因此,我对Riffle Shuffle算法的渐近速度有疑问,需要找到最佳情况,最坏情况,典型情况和空间复杂度。有谁可以帮我离开这里吗?干杯
[假设唯一的元素,Riffle Shuffle算法始终以最佳状态运行相同的时间,更糟糕的情况是O(n)时间,由于空间的复杂性,我不太熟悉该算法,因为也许有某种方法可以做到在适当的位置具有O(1)空间,但是将列表分为两半并在下半年进行迭代以完成工作的基本方法也具有O(n)空间复杂度
O(n)
O(1)