の時間の複雑さは何ですか
(1) 長さ N のリストをランダムにシャッフルしますか?
(2) N 個のアイテムのセットからアイテムをランダムに N 回選択しますか?
2 に答える
2
シャッフル アルゴリズムと意図した動作によって異なります。たとえば、iTunes シャッフルは、シャッフルすると別のプレイリストの順序を作成し、それによってすべての曲をすぐにシャッフルするだけでなく、繰り返し可能なプレイリストの順序も作成します (プレイリストを 2 回聞いた場合、同じ曲が互いに続きます)。各曲の前に新しいシードを選択し、再生を開始するときに選択することでトラックを完全にシャッフルできます。ただし、時間の複雑さは本質的に両方で同じであり、どちらの場合も無視できます。
ただし、理論的には、どちらも O(nr) の時間複雑度です (ここで、r は乱数アルゴリズムの時間複雑度です)。
于 2012-08-23T18:57:33.620 に答える
1
リストのシャッフルは O(n)
サイズ n のリストから n 個のものをランダムに選択することも O(n) です。
曲のリストは必ずしも永遠に同じであるとは限らないため、再生ごとにランダムに何かを選択する方がおそらく良いでしょう. このような場合、事前計算をやり直す必要があります。
于 2012-08-23T21:30:42.500 に答える