アルゴリズムが次の場合、計算の複雑さはどのように定義されますか?
- ...多くの結果が得られますか? 合計として（その場合、セットを生成するアルゴリズムはO(k)
kよりも高速になることはできません）、または要素ごとに（推定値を乗算して、セットを生成しないアルゴリズムと比較する必要があります）？- ストレージの複雑さについてはどうですか? セット全体を一度にメモリに存在させる必要があるのか、それとも連続する各要素を生成して破棄できるのか、見積もりに反映されますか?
- ...複数のパラメータがありますか? パラメータごとに個別の数値か、それとも何かを組み合わせたものか?
両方のケースに適した例は、kからの要素の選択Nです。例えば、工程が必要かどう~kかで見積もりに違いはありますか？~N
これらの場合の用語の正式な定義、および/または単なるランダムな考えや個人的な経験ではなく、CS論文でこれらのあいまいさがどのように排除されているかなど、いくつかの確固たる証拠を見たいと思います. 目標は、完全で最先端の解決策を見つけて、私の (および他の) テキストからこれらのあいまいさを完全になくすことです。
これについて私が困惑した質問は次のとおりです。O(1) の一意の (繰り返さない) 乱数? , 0 と上限 N の間の K 個の非反復整数のリストを効率的に生成するにはどうすればよいですか? 単一のランダムな値の組み合わせを選択するアルゴリズム? 、リンクされたリストから一連のランダムな要素を効率的に選択します。