Big O Notation: フローチャートを使用した時間計算量の理解

JavaScript における Big-O の複雑さに関する Edison の投稿を強くお勧めします。これは、このトピックに関して私が見た中で最も親切な記事です。

記事は利用できなくなりました

ここでは、フローチャートを使用して Big-O の時間計算量を視覚化する際に、エジソンからポイントを得ます。

ログ(n)

対数時間

時間計算量を視覚的に理解するには、イテレータ (i*2 など) を確認し、関数に含まれるループの数を確認します。

の上）

線形時間



線形時間と対数時間は似ていますが、ループの条件により出力は異なります。 exampleLogarithmic(100) は 1、2、4、8、16、32、64 を返しますが、exampleLinear(100) は単純に 100 未満のすべての正の整数をループします。

O(n^2)

二次時間



ループの数は、n を累乗する指数と一致します。文字通り、時間の複雑さが増加するにつれて関数が大きくなるのがわかります。

O(n^3)

立方時間



これは時間計算量を理解する唯一の方法ではありませんが、時間計算量が増加するにつれて関数が文字通り長くなるのを確認することは非常に役立ちます。場合によっては、白黒で書かれたコードが

 で表示されることがあります。ブロックは視覚的な学習者に要点を伝えません。

<p>それでは、クイズをしてみましょう。この関数の時間計算量はどれくらいですか?</p>

<p>あなたの推測を立ててください...<br><br>
<img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173601046526425.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Big O Notation: Understanding Time Complexity using Flowcharts"><br><br>
直線的ですね！ループが 1 つあり、反復子によってループが整数をスキップしないため、それがわかります。</p>

<p>この関数の時間計算量はどれくらいですか?<br><br>
<img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173601046682236.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Big O Notation: Understanding Time Complexity using Flowcharts"><br><br>
自分自身を疑わないでください。これは最初の例とは少し異なりますが、線形時間計算量を持っています。</p>

<p>この関数の時間計算量はどれくらいですか?<br><br>
<img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173601046719860.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Big O Notation: Understanding Time Complexity using Flowcharts"><br><br>
ここでパターンが見られるかもしれません。直線的です!</p><p>さて、私の論理の流れを理解しているなら、これはひっかけの質問かもしれません:<br><br>
<img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173601046876014.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Big O Notation: Understanding Time Complexity using Flowcharts"></p>

<p>ループの回数は指数 n で表されると言いました。では、なぜこれは 2 次ではなく線形の時間計算量をもつのでしょうか?</p>

<p>別の for ループの中に for ループがある場合、これは 2 次の時間計算量になります。ただし、ある for ループが<em>後に</em>実行される別の for ループの時間計算量は二次ではなく線形です。</p>

<p>それでは、この関数の時間計算量はどれくらいですか?<br><br>
<img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173601046913700.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Big O Notation: Understanding Time Complexity using Flowcharts"><br><br>
ここでは難しいことは何もありません。これには二次時間計算量があります。</p>

<p>さて、最後の質問ですが、他のすべての質問を問う質問です。この関数の時間計算量は何ですか?<br><br>
<img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173601047060673.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Big O Notation: Understanding Time Complexity using Flowcharts"><br><br>
for ループの条件とループの膨大な数に注目していただければ幸いです。これには、ループ条件 i<n>

<p>この投稿の画像は自分のアプリで生成しました。その開発プロセスについては別の投稿で説明しました。</p>

<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173601047160481.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Big O Notation: Understanding Time Complexity using Flowcharts">[</p>

<h2>
  
  
  ライトハウスで100を達成する方法
</h2>

<h3>
  
  
  ender minyard ・ 8月 30 2020 ・ 2 分読み取り
</h3>

<h2>
  
  
  webperf#速度#javascript#webdev
</h2>

<p>](/ender_minyard/how-i-got-100-on-lighthouse-2icd)</p>


          

            
        </n></p>

以上がBig O Notation: フローチャートを使用した時間計算量の理解の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。