DSA と Big O 記法についての紹介

Sep 19, 2024 pm 08:30 PM

Intro to DSA & Big O Notation

DSA をマスターするための注意事項:

マスター DSA は、S/W Er に提供される高額給与の「資格」を獲得します。
DSA はソフトウェア エンジニアリングの主要部分です。
コードを記述する前に、全体像を理解し、詳細を掘り下げてください。
概念を視覚的に理解し、DSA は言語に依存しないため、それらの概念を任意の l/g 経由でコードに変換することがすべてです。
今後のコンセプトはすべて、何らかの形で以前のコンセプトとリンクしています。したがって、練習してコンセプトを徹底的にマスターするまでは、トピックを飛び回ったり、先に進んだりしないでください。
概念を視覚的に学ぶと、内容をより深く理解できるようになり、その結果、知識をより長期間保持することができます。
これらのアドバイスに従えば、失うものは何もありません。

Linear DS:
Arrays
LinkedList(LL) & Doubly LL (DLL)
Stack
Queue & Circular Queue

Non-linear DS:
Trees
Graphs
ログイン後にコピー

ビッグオー表記

アルゴのパフォーマンス比較には、この表記法を理解することが不可欠です。
これは、アルゴの効率を比較するための数学的な方法です。

時間計算量

コードの実行速度が速くなるほど、速度は低くなります
V. ほとんどのインタビューに同意します。

空間の複雑さ

ストレージコストが低いため、時間の複雑さに比べてほとんど考慮されません。
面接官がこの点からも質問する可能性があるため、理解する必要があります。

3 つのギリシャ文字:

  1. オメガ
  2. シータ
  3. オミクロン、つまりビッグオー [最も頻繁に見られる]

アルゴリズムの事例

  1. 最良のケース [Omega を使用して表現]
  2. 平均ケース [Theta を使用して表現]
  3. 最悪のケース [Omicron を使用して表す]

技術的には、平均的なケース Big-O に匹敵する最良のケースはありません。それぞれオメガとシータを使用して表されます。
私たちは常に最悪のケースを測定しています。

## O(n): Efficient Code
Proportional
Its simplified by dropping the constant values.
An operation happens 'n' times, where n is passed as an argument as shown below.
Always going to be a straight line having slope 1, as no of operations is proportional to n.
X axis - value of n.
Y axis - no of operations 

// O(n)
function printItems(n){
  for(let i=1; i<=n; i++){
    console.log(i);
  }
}
printItems(9);

// O(n) + O(n) i.e O(2n) operations. As we drop constants, it eventually becomes O(n)
function printItems(n){
  for(let i=0; i<n; i++){
    console.log(i);
  }
  for(let j=0; j<n; j++){
    console.log(j);
  }
}
printItems(10);
ログイン後にコピー
## O(n^2):
Nested loops.
No of items which are output in this case are n*n for a 'n' input.
function printItems(n){
  for(let i=0; i<n; i++){
    console.log('\n');
    for(let j=0; j<n; j++){
      console.log(i, j);
    }
  }
}
printItems(4);
ログイン後にコピー
## O(n^3):
No of items which are output in this case are n*n*n for a 'n' input.
// O(n*n*n)
function printItems(n){
  for(let i=0; i<n; i++){
    console.log(`Outer Iteration ${i}`);
    for(let j=0; j<n; j++){
      console.log(`  Mid Iteration ${j}`);
      for(let k=0; k<n; k++){
        //console.log("Inner");
        console.log(`    Inner Iteration ${i} ${j} ${k}`);
      }
    }
  }
}
printItems(3);


## Comparison of Time Complexity:
O(n) > O(n*n)


## Drop non-dominants:
function xxx(){
  // O(n*n)
  Nested for loop

  // O(n)
  Single for loop
}
Complexity for the below code will O(n*n) + O(n) 
By dropping non-dominants, it will become O(n*n) 
As O(n) will be negligible as the n value grows. O(n*n) is dominant term, O(n) is non-dominnat term here.
ログイン後にコピー
## O(1):
Referred as Constant time i.e No of operations do not change as 'n' changes.
Single operation irrespective of no of operands.
MOST EFFICIENT. Nothing is more efficient than this. 
Its a flat line overlapping x-axis on graph.


// O(1)
function printItems(n){
  return n+n+n+n;
}
printItems(3);


## Comparison of Time Complexity:
O(1) > O(n) > O(n*n)
ログイン後にコピー
## O(log n)
Divide and conquer technique.
Partitioning into halves until goal is achieved.

log(base2) of 8 = 3 i.e we are basically saying 2 to what power is 8. That power denotes the no of operations to get to the result.

Also, to put it in another way we can say how many times we need to divide 8 into halves(this makes base 2 for logarithmic operation) to get to the single resulting target item which is 3.

Ex. Amazing application is say for a 1,000,000,000 array size, how many times we need to cut to get to the target item.
log(base 2) 1,000,000,000 = 31 times
i.e 2^31 will make us reach the target item.

Hence, if we do the search in linear fashion then we need to scan for billion items in the array.
But if we use divide & conquer approach, we can find it in just 31 steps.
This is the immense power of O(log n)

## Comparison of Time Complexity:
O(1) > O(log n) > O(n) > O(n*n)
Best is O(1) or O(log n)
Acceptable is O(n)
ログイン後にコピー
O(n log n) : 
Used in some sorting Algos.
Most efficient sorting algo we can make unless we are sorting only nums.
ログイン後にコピー
Tricky Interview Ques: Different Terms for Inputs.
function printItems(a,b){
  // O(a)
  for(let i=0; i<a; i++){
    console.log(i);
  }
  // O(b)
  for(let j=0; j<b; j++){
    console.log(j);
  }
}
printItems(3,5);

O(a) + O(b) we can't have both variables equal to 'n'. Suppose a is 1 and b is 1bn.
Then both will be very different. Hence, it will eventually be O(a + b) is what can call it.
Similarly if these were nested for loops, then it will become O(a * b)
ログイン後にコピー
## Arrays
No reindexing is required in arrays for push-pop operations. Hence both are O(1).
Adding-Removing from end in array is O(1)

Reindexing is required in arrays for shift-unshift operations. Hence, both are O(n) operations, where n is no of items in the array.
Adding-Removing from front in array is O(n)

Inserting anywhere in array except start and end positions:
myArr.splice(indexForOperation, itemsToBeRemoved, ContentTobeInsterted)
Remaining array after the items has to be reindexed.
Hence, it will be O(n) and not O(0.5 n) as Big-O always meassures worst case, and not avg case. 0.5 is constant, hence its droppped.
Same is applicable for removing an item from an array also as the items after it has to be reindexed.


Finding an item in an array:
if its by value: O(n)
if its by index: O(1)

Select a DS based on the use-case.
For index based, array will be a great choice.
If a lot of insertion-deletion is perform in the begin, then use some other DS as reindexing will make it slow.
ログイン後にコピー

n=100 の時間計算量の比較:

O(1) = 1
O(log 100) = 7
O(100) = 100
O(n^2) = 10,000

n=1000 の時間計算量の比較:

O(1) = 1
O(log 1000) = ~10
O(1000) = 1000
O(1000*1000) = 1,000,000

主に次の 4 つに焦点を当てます:
Big O(n*n): ネストされたループ
Big O(n): 比例
Big O(log n): 分割統治
Big O(1): 定数

O(n!) は通常、意図的に悪いコードを書いたときに発生します。
O(n*n) は恐ろしいアルゴです
O(n log n) は許容され、特定の並べ替えアルゴリズムで使用されます
O(n) : 許容されます
O(log n)、O(1) : 最高

空間の複雑さはすべての DS、つまり O(n) でほぼ同じです。
空間複雑度は、ソートアルゴリズムを使用すると、O(n) から O(log n) または O(1) まで変化します

時間計算量はアルゴリズムによって異なります

文字列などの数値以外のソートの最適な時間計算量は、Quick、Merge、Time、Heap ソートでは O(n log n) です。

学んだことを応用する最善の方法は、できる限りコーディングすることです。

各 DS の長所と短所に基づいて、どの問題ステートメントでどの DS を選択するかを選択します。

詳細については、bigoheatsheet.com を参照してください

以上がDSA と Big O 記法についての紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホット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衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

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

Python vs. JavaScript:学習曲線と使いやすさ Python vs. JavaScript:学習曲線と使いやすさ Apr 16, 2025 am 12:12 AM

Pythonは、スムーズな学習曲線と簡潔な構文を備えた初心者により適しています。 JavaScriptは、急な学習曲線と柔軟な構文を備えたフロントエンド開発に適しています。 1。Python構文は直感的で、データサイエンスやバックエンド開発に適しています。 2。JavaScriptは柔軟で、フロントエンドおよびサーバー側のプログラミングで広く使用されています。

C/CからJavaScriptへ:すべてがどのように機能するか C/CからJavaScriptへ:すべてがどのように機能するか Apr 14, 2025 am 12:05 AM

C/CからJavaScriptへのシフトには、動的なタイピング、ゴミ収集、非同期プログラミングへの適応が必要です。 1)C/Cは、手動メモリ管理を必要とする静的に型付けられた言語であり、JavaScriptは動的に型付けされ、ごみ収集が自動的に処理されます。 2)C/Cはマシンコードにコンパイルする必要がありますが、JavaScriptは解釈言語です。 3)JavaScriptは、閉鎖、プロトタイプチェーン、約束などの概念を導入します。これにより、柔軟性と非同期プログラミング機能が向上します。

JavaScriptとWeb:コア機能とユースケース JavaScriptとWeb:コア機能とユースケース Apr 18, 2025 am 12:19 AM

Web開発におけるJavaScriptの主な用途には、クライアントの相互作用、フォーム検証、非同期通信が含まれます。 1)DOM操作による動的なコンテンツの更新とユーザーインタラクション。 2)ユーザーエクスペリエンスを改善するためにデータを提出する前に、クライアントの検証が実行されます。 3)サーバーとのリフレッシュレス通信は、AJAXテクノロジーを通じて達成されます。

JavaScript in Action:実際の例とプロジェクト JavaScript in Action:実際の例とプロジェクト Apr 19, 2025 am 12:13 AM

現実世界でのJavaScriptのアプリケーションには、フロントエンドとバックエンドの開発が含まれます。 1)DOM操作とイベント処理を含むTODOリストアプリケーションを構築して、フロントエンドアプリケーションを表示します。 2)node.jsを介してRestfulapiを構築し、バックエンドアプリケーションをデモンストレーションします。

JavaScriptエンジンの理解:実装の詳細 JavaScriptエンジンの理解:実装の詳細 Apr 17, 2025 am 12:05 AM

JavaScriptエンジンが内部的にどのように機能するかを理解することは、開発者にとってより効率的なコードの作成とパフォーマンスのボトルネックと最適化戦略の理解に役立つためです。 1)エンジンのワークフローには、3つの段階が含まれます。解析、コンパイル、実行。 2)実行プロセス中、エンジンはインラインキャッシュや非表示クラスなどの動的最適化を実行します。 3)ベストプラクティスには、グローバル変数の避け、ループの最適化、constとletsの使用、閉鎖の過度の使用の回避が含まれます。

Python vs. JavaScript:コミュニティ、ライブラリ、リソース Python vs. JavaScript:コミュニティ、ライブラリ、リソース Apr 15, 2025 am 12:16 AM

PythonとJavaScriptには、コミュニティ、ライブラリ、リソースの観点から、独自の利点と短所があります。 1)Pythonコミュニティはフレンドリーで初心者に適していますが、フロントエンドの開発リソースはJavaScriptほど豊富ではありません。 2)Pythonはデータサイエンスおよび機械学習ライブラリで強力ですが、JavaScriptはフロントエンド開発ライブラリとフレームワークで優れています。 3)どちらも豊富な学習リソースを持っていますが、Pythonは公式文書から始めるのに適していますが、JavaScriptはMDNWebDocsにより優れています。選択は、プロジェクトのニーズと個人的な関心に基づいている必要があります。

Python vs. JavaScript:開発環境とツール Python vs. JavaScript:開発環境とツール Apr 26, 2025 am 12:09 AM

開発環境におけるPythonとJavaScriptの両方の選択が重要です。 1)Pythonの開発環境には、Pycharm、Jupyternotebook、Anacondaが含まれます。これらは、データサイエンスと迅速なプロトタイピングに適しています。 2)JavaScriptの開発環境には、フロントエンドおよびバックエンド開発に適したnode.js、vscode、およびwebpackが含まれます。プロジェクトのニーズに応じて適切なツールを選択すると、開発効率とプロジェクトの成功率が向上する可能性があります。

JavaScript通訳者とコンパイラにおけるC/Cの役割 JavaScript通訳者とコンパイラにおけるC/Cの役割 Apr 20, 2025 am 12:01 AM

CとCは、主に通訳者とJITコンパイラを実装するために使用されるJavaScriptエンジンで重要な役割を果たします。 1)cは、JavaScriptソースコードを解析し、抽象的な構文ツリーを生成するために使用されます。 2)Cは、Bytecodeの生成と実行を担当します。 3)Cは、JITコンパイラを実装し、実行時にホットスポットコードを最適化およびコンパイルし、JavaScriptの実行効率を大幅に改善します。

See all articles