2

私が最近見たプログラミング課題の一環として、生徒たちはパズルを解くための関数の大きな O 値を見つけるように求められました。退屈だったので、自分でプログラムを書くことにしました。ただし、私のソリューションでは、問題で見たパターンを使用して、計算の大部分をスキップします。

Big O は、スケーリングに基づいて時間がどのように増加するかを示していますが、スケーリングnとしてn、パターンのリセットに達すると、かかる時間も低い値にリセットされます。私の考えでは、それがO(nlogn % k)いつk+1リセットされるかということでした。もう 1 つの考えは、ハード リミットがあるため、値は ですO(1)。これは、任意の定数の大きな O であるためです。それらの 1 つは正しいですか? そうでない場合、制限はどのように表現されるべきですか?

リセットの例として、k値は 31336 です。n=31336 では 31336 ステップかかりますが、n=31337 では 1 かかります。

コードは次のとおりです。

def Entry(a1, q):
    F = [a1]
    lastnum = a1
    q1 = q % 31336
    rows = (q / 31336)
    for i in range(1, q1):
        lastnum = (lastnum * 31334) % 31337
        F.append(lastnum)

    F = MergeSort(F)
    print lastnum * rows + F.index(lastnum) + 1

MergeSortO(nlogn)複雑な標準マージソートです。

4

3 に答える 3

2

さて、big-O 問題を考えるのに私がよく使う簡単な方法は、n を非常に大きく、無限に等しいと考えることです。非常に大きな数値でのバイトレベルの操作に特にこだわらない場合 (q % 31336 は、q が無限大になり、実際には一定ではないため)、O(1) であるという直感は正しいです。

q を無限大に近いと想像すると、q % 31336 は明らかに 0 から 31335 の間にあることがわかります。この事実により、配列要素の数が制限され、ソート時間が一定量 (n * log(n) ==> 31335 * log(31335) * C、定数 C の場合) に制限されます。したがって、アルゴリズム全体で一定の時間です。

しかし、現実の世界では、乗算、除算、モジュラスはすべて、入力サイズに基づいてスケーリングされます。それを理解することに興味がある場合は、からつばアルゴリズムを調べることができます。演習として残しておきます。

于 2013-10-23T23:36:41.687 に答える
2

これは Big O の定義O(1)から導き出すことができます。がソリューションの複雑さである場合、次のようになります。f(x)

式 2

と

式 2

と任意M > 470040の（それはのnlognためですn = 31336）とx > 0。そして、これは定義から次のことを意味します。

式 1

于 2013-10-23T23:36:43.363 に答える
-2

この問題のいくつかの異なるインスタンスがあり、それぞれに独自のk値がある場合、メソッドの複雑さは O(1) ではなく、O(k·ln k).

于 2013-10-24T00:13:11.013 に答える