1

私はC＃4.0で作業していますが、次の問題があります。

実数の有限集合Sとパラメーターk（必ずしも集合内ではない）が与えられた場合、k以上のSの最小数を見つけます。

明らかに、バランスの取れた二分木を使用してそうすることができます。ただし、C＃にはそのようなデータ構造の実装はありません。アルゴリズムのオプションとC＃での可能な実装は何ですか？

編集：

ほとんどの人は実際に助けるよりも批判することに興味があるので、私はもっと説明します：

これは、実関数を数百万のピース（またはヒストグラムのようなビン）に分割するアルゴリズム用であり、kを含むピースを見つけて、それに何らかの計算を適用する効率的な方法を見つける必要があります。ピースは、フォームの実際の間隔です[a; b）重複しないでください。

私が設計している方法は、kが与えられた場合にピースを取得する必要があり、1秒間に数千回呼び出される必要があるため、パフォーマンスが重要です。したがって、O（n）検索は受け入れられません。

Sのデータ構造の構築に費やされる時間は重要ではなく、重要でもありません。これは、セットが1回だけ構築され、変更されることはないためです（これは不変のセットです）。

O（log n）検索の複雑さを持つ赤黒木を使用できることはわかっています。ただし、他のアルゴリズムオプションを調査したいと思います（おそらくC＃の既存の実装を使用して）。

4

4 に答える 4

2

この問題は、O（n）時間で解決するのは簡単です。すべての要素をループし、基準を満たす（kより小さくない）これまでに見つかった最小の要素を追跡します。

異なるkで繰り返される場合：ソートされた配列の二分探索O（log n）

最大要素サイズが制限されている場合、アーキテクチャのようなバケットソートはO（1）時間を与えます。

于 2012-10-10T20:20:48.230 に答える
2

最も簡単な方法は（O(N)）：

double k = 3.5;
List<double> S = new List<double>() { 1, 3, 5, 7, 9, 2, 4, 5, 6, 8, 10 };

var min = S.Where(f => f >= k).Min(); //4

リストがすでにソートされている場合、コストはO(LogN)

List<double> S = new List<double>() { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

var index = S.BinarySearch(k);
var min = index > 0 ? S[index] : S[~index];
于 2012-10-10T20:27:11.330 に答える
1

さて、あなたはSCG.SortedSetを使うことができます、それはカバーの下で、赤黒木です。

SCG.Listまたは配列を使用して並べ替え、BinarySearch（）メソッドを使用できます。

C5コレクションライブラリも使用できます。

これが宿題の場合は、独自の実装を作成できます（教授が望んでいる可能性が高いと思います）。そこにはたくさんのオプションがあります。

于 2012-10-10T20:27:25.027 に答える
0

「最速」ではありませんが、「SortedList十分に速い」可能性があります。

public static class Extensions
{
    public static double FindSmallestGreaterThan(this SortedList<double,double> list, double value)
    {
       foreach(double d in list.Keys)
       {
           if(d > value) return d;
       }
       throw new IndexOutOfRangeException("No values in the list greater than " + value.ToString());
    }
}

使用法は次のようになります：

SortedList<double,double> list = new SortedList<double,double>();
list.Add(0.5, 0.5);
list.Add(1.9, 1.9);

double d = list.FindSmallestGreaterThan(1.0);
于 2012-10-10T20:25:58.830 に答える