検索
ホームページバックエンド開発Python チュートリアル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 



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

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

<p>2 番目に、factor_asc とfactor_desc という 2 つの配列を作成します。ここでの魔法は、要素をfactors_ascに追加することです。要素は自動的に昇順になるため、このように名前が付けられています。<br>
factors_asc に何かを追加するときは、n をその値で割って、factor_desc に追加します。ここでも同様のロジックです。これらは降順で追加されるので便利です。</p><p>次に、ループを開始します。ここでは、n のルートに到達すると停止するため、while i * i 

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

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

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

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

<p>まず、if k 

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

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

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

<h2>
  
  
  カーブ
</h2>

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

<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173598658415895.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="The Kth factor of N - an O(sqrt n) algorithm"><br>
<em>Mathspace で入手可能</em></p>

<h2>
  
  
  結論
</h2>

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

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

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


          

            
        

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

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
HTMLを解析するために美しいスープを使用するにはどうすればよいですか?HTMLを解析するために美しいスープを使用するにはどうすればよいですか?Mar 10, 2025 pm 06:54 PM

この記事では、Pythonライブラリである美しいスープを使用してHTMLを解析する方法について説明します。 find()、find_all()、select()、およびget_text()などの一般的な方法は、データ抽出、多様なHTML構造とエラーの処理、および代替案(SEL

Pythonの数学モジュール:統計Pythonの数学モジュール:統計Mar 09, 2025 am 11:40 AM

Pythonの統計モジュールは、強力なデータ統計分析機能を提供して、生物統計やビジネス分析などのデータの全体的な特性を迅速に理解できるようにします。データポイントを1つずつ見る代わりに、平均や分散などの統計を見て、無視される可能性のある元のデータの傾向と機能を発見し、大きなデータセットをより簡単かつ効果的に比較してください。 このチュートリアルでは、平均を計算し、データセットの分散の程度を測定する方法を説明します。特に明記しない限り、このモジュールのすべての関数は、単に平均を合計するのではなく、平均()関数の計算をサポートします。 浮動小数点数も使用できます。 ランダムをインポートします インポート統計 fractiから

Pythonオブジェクトのシリアル化と脱介入:パート1Pythonオブジェクトのシリアル化と脱介入:パート1Mar 08, 2025 am 09:39 AM

Pythonオブジェクトのシリアル化と脱介入は、非自明のプログラムの重要な側面です。 Pythonファイルに何かを保存すると、構成ファイルを読み取る場合、またはHTTPリクエストに応答する場合、オブジェクトシリアル化と脱滑り化を行います。 ある意味では、シリアル化と脱派化は、世界で最も退屈なものです。これらすべての形式とプロトコルを気にするのは誰ですか? Pythonオブジェクトを維持またはストリーミングし、後で完全に取得したいと考えています。 これは、概念レベルで世界を見るのに最適な方法です。ただし、実用的なレベルでは、選択したシリアル化スキーム、形式、またはプロトコルは、プログラムの速度、セキュリティ、メンテナンスの自由、およびその他の側面を決定する場合があります。

TensorflowまたはPytorchで深い学習を実行する方法は?TensorflowまたはPytorchで深い学習を実行する方法は?Mar 10, 2025 pm 06:52 PM

この記事では、深い学習のためにTensorflowとPytorchを比較しています。 関連する手順、データの準備、モデルの構築、トレーニング、評価、展開について詳しく説明しています。 特に計算グラップに関して、フレームワーク間の重要な違い

人気のあるPythonライブラリとその用途は何ですか?人気のあるPythonライブラリとその用途は何ですか?Mar 21, 2025 pm 06:46 PM

この記事では、numpy、pandas、matplotlib、scikit-learn、tensorflow、django、flask、and requestsなどの人気のあるPythonライブラリについて説明し、科学的コンピューティング、データ分析、視覚化、機械学習、Web開発、Hの使用について説明します。

LinuxターミナルでPythonバージョンを表示するときに発生する権限の問題を解決する方法は?LinuxターミナルでPythonバージョンを表示するときに発生する権限の問題を解決する方法は?Apr 01, 2025 pm 05:09 PM

LinuxターミナルでPythonバージョンを表示する際の許可の問題の解決策PythonターミナルでPythonバージョンを表示しようとするとき、Pythonを入力してください...

美しいスープでPythonでWebページを削る:検索とDOMの変更美しいスープでPythonでWebページを削る:検索とDOMの変更Mar 08, 2025 am 10:36 AM

このチュートリアルは、単純なツリーナビゲーションを超えたDOM操作に焦点を当てた、美しいスープの以前の紹介に基づいています。 HTML構造を変更するための効率的な検索方法と技術を探ります。 1つの一般的なDOM検索方法はExです

Pythonでコマンドラインインターフェイス(CLI)を作成する方法は?Pythonでコマンドラインインターフェイス(CLI)を作成する方法は?Mar 10, 2025 pm 06:48 PM

この記事では、コマンドラインインターフェイス(CLI)の構築に関するPython開発者をガイドします。 Typer、Click、Argparseなどのライブラリを使用して、入力/出力の処理を強調し、CLIの使いやすさを改善するためのユーザーフレンドリーな設計パターンを促進することを詳述しています。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

VSCode Windows 64 ビットのダウンロード

VSCode Windows 64 ビットのダウンロード

Microsoft によって発売された無料で強力な IDE エディター

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

EditPlus 中国語クラック版

EditPlus 中国語クラック版

サイズが小さく、構文の強調表示、コード プロンプト機能はサポートされていません

MantisBT

MantisBT

Mantis は、製品の欠陥追跡を支援するために設計された、導入が簡単な Web ベースの欠陥追跡ツールです。 PHP、MySQL、Web サーバーが必要です。デモおよびホスティング サービスをチェックしてください。

mPDF

mPDF

mPDF は、UTF-8 でエンコードされた HTML から PDF ファイルを生成できる PHP ライブラリです。オリジナルの作者である Ian Back は、Web サイトから「オンザフライ」で PDF ファイルを出力し、さまざまな言語を処理するために mPDF を作成しました。 HTML2FPDF などのオリジナルのスクリプトよりも遅く、Unicode フォントを使用すると生成されるファイルが大きくなりますが、CSS スタイルなどをサポートし、多くの機能強化が施されています。 RTL (アラビア語とヘブライ語) や CJK (中国語、日本語、韓国語) を含むほぼすべての言語をサポートします。ネストされたブロックレベル要素 (P、DIV など) をサポートします。