N の K 番目の因数 - O(sqrt n) アルゴリズム

導入

最近、私は「Big O Notation を学ぶ」という記事をきっぱり書きました。この投稿では、Big-O チートシートで利用できる Big O 時間表記のすべてのタイプについて説明します。そして、この 7 つ以外にこれ以上の時間表記が可能になるとは思いませんでした。

あたかも宇宙自体が私を謙虚にし、私の無知を嘲笑しているかのように、私は O(√n) 時間で解決できる LeetCode の問題に遭遇しました。 気が狂っているなら、これは O(N^1/2) と訳せるかもしれません。

問題

2 つの正の整数 n と k が与えられます。整数 n の因数は、n % i == 0 である整数 i として定義されます。

昇順でソートされた n のすべての因子のリストを検討し、このリストの k 番目の因子を返すか、n の因子が k 未満の場合は -1 を返します。

明らかな解決策

そうですね、あなたが私と同じなら、最初に 1 から n までのすべての数値を調べて、それが因数であるかどうかを確認し、それが目的の k インデックスに含まれている場合はそれを返すことを考えるでしょう。

コードは次のようになります:

def getkthFactorOfN(n, k):
    result = 0
    for i in range(1, n + 1):
        if n % i == 0:
            result = result + 1
            if result == k:
                return i
    return -1

これはすべて問題なく、ダンディですが、「のみ」 O(n) です。結局、ループは1つしかなく、n 1まで進みます。
時間表記を考慮する場合、他の操作はすべて破棄されます。

しかし、友よ、落とし穴があります。

要因の理解

よく考えてみると、ある時点以降、因子は「ミラーリング」されます。

たとえば、81 という数字を考えてみましょう。その因数は [1, 3, 9, 27] です。ここで、

• 1 * 81 = 81
• 3 * 27 = 81
• 9 * 9 = 81
• 27 * 3 = 81
• 81 * 1 = 81

数字の9を数えなければ、操作は単純に繰り返され、反転されます。 n をその因数の 1 つで割ると、別の因数が得られます。
n の平方根を求めます。n 自体を 2 乗したものです (当然です)。

この知識を身につければ、ループを最大 n 回 (range(1, n 1) で) 反復する必要はなく、単に math.sqrt(n) まで反復する必要があることがわかります。その後、必要な要素はすべて揃っています!

それほど明白ではない解決策

必要なものがすべて揃ったので、このループを 1 -> に変換する必要があります。 n から 1 -> sqrt n.

ここにコードを投げて、1 行ずつ見ていきます。

def getkthFactorOfN(n, k):
    i = 1
    factors_asc = []
    factors_desc = []
    while i * i <= n:
        if n % i == 0:
            factors_asc.append(i)
            if i != n // i:
                factors_desc.append(n // i)
        i += 1
    if k <= len(factors_asc):
        return factors_asc[k-1]
    k -= len(factors_asc)
    if k <= len(factors_desc):
        return factors_desc[-k]
    return -1

ああ、それはもっと複雑です。細かく見てみましょう:

まず、i = 1 を初期化します。この変数は、因子を検索するときに「現在の数値」として使用されます。

2 番目に、factor_asc とfactor_desc という 2 つの配列を作成します。ここでの魔法は、要素をfactors_ascに追加することです。要素は自動的に昇順になるため、このように名前が付けられています。
factors_asc に何かを追加するときは、n をその値で割って、factor_desc に追加します。ここでも同様のロジックです。これらは降順で追加されるので便利です。

次に、ループを開始します。ここでは、n のルートに到達すると停止するため、while i * i

現在の数値が因数 (n % i == 0) であるかどうかを確認することから始めます。そうであれば、それをfactor_asc配列に追加できます。

次に、i の「逆因数」を求めます。これは、 i != n // i かどうか、つまりルートではないかどうかをチェックすることで実行できます。これは、両方の配列でルートが重複してはいけないためです。そうでない場合は、 n // i を実行し、その結果をfactor_desc.

に追加することで、逆の係数を取得します。

その後、i に 1 を加えてループを続けます。

ループが完了したら、必要な階乗をすべて取得する必要があります。

まず、if k

そうでない場合は、見つかった因子の量を k から減算し、k -= len(factors_asc) および k

k がfactors_desc 内にある場合は、factors_desk[-k] でその値を取得します (最後から最初へ)。

すべてが失敗した場合は、-1 を返します。

カーブ

曲線グラフのどこに到達するのか疑問に思うなら、それは O(n) と O(log n) の間であり、前者よりも良く、悪くなります。後者よりも。これがグラフです:

Mathspace で入手可能

結論

これは発見と研究のための乗り物でした。ここまで読んでいただき、誠にありがとうございました。

さらに最適化したい場合は、factor_asc_len 変数とfactor_desc_len 変数を作成し、これらの配列に値を追加するたびに 1 を加算します。これにより、メソッド len() を呼び出す必要がなくなります。このメソッドは次のとおりです。 O(n) そのため、時間表記に影響を与える可能性があります。

次回まで、勉強頑張ってください!

以上がN の K 番目の因数 - O(sqrt n) アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。