私はNxNブール行列を持っています。そのすべての要素は初期状態を持っていますfalse
bool[][] matrix = GetMatrix(N);
ループの各ステップで、row i, column jすべてのセルから 1 つのセル ( ) を一様にランダムに選択し、何らかの条件が発生falseするまでそれを設定します。true
どの方法を使用しますか? 私はこの2つの方法を念頭に置いています。
NxNから配列を作成し、0...(NxN-1)この配列から i 要素を順次取得して行列 [i/N][i%N] を設定するよりも、一様シャッフル アルゴリズムを使用してシャッフルします。
O(N^2)余分なメモリを使用し、初期化にO(N^2)時間がかかります
そして第二に
iから乱数を生成し0...(N^2-1)、(i/N, i%N) が行列に設定されている場合、設定されていない要素が見つかるまで乱数生成を繰り返します。
この方法では追加のメモリは使用されませんが、パフォーマンスを見積もるのは困難です... 1 つを除くすべての要素が設定されていて、空きセルを探してランダムに何度も繰り返される場合がありますか? ランダムが理論的に一様に機能するとすぐに、このケースはそれほど頻繁に発生するべきではないというのは正しいですか?