私が5のように私に説明してください:時間複雑さ

私が5歳のように私に説明してください：

時間複雑度
皆さんこんにちは!畝
時間の複雑さは単にプログラムがそのタスクを完了するのにかかる時間の尺度です.時間の複雑さは、プログラミング中にあらゆる点で重要な役割を果たしている.では、今すぐシンプルにして学びましょう.

内容

・How to find time complexity?・

・Understanding asymptotic analysis・

・Analysis of Big-O complexities・

・Big-O cheatsheet・

・Do we consider time complexity of in-built functions?・

・Time complexity of conditional statements・

時間複雑性を見つける方法？

どのアルゴリズムが我々の仕事のためによりよいかについて確認するために、1つの通常の方法は我々のコンピュータの両方のアルゴリズムを走らせて、1つがより少ない時間をとっている点に注意することです.しかし、時間の複雑さを見つける方法は、結果がデバイスのパフォーマンスのような要因、入力されたものに依存するので、効果的でありません.
漸近解析では,与えられた入力サイズに基づいて性能を評価した.すなわち、アルゴリズムによって実行される基本ステップ数をカウントして実行を終了させることによって時間複雑性を推定する.
より良い方法でこれを理解する例を見てみましょう.
第1ケース

//psuedocode
int i = 1 to N
N = N + N
print N

2番目のケース

//pseudocode
return N * N

最初の場合では、時間はNに依存する.第2の場合では、我々が取るNのどんな値も、1ステップ(Nに依存しない)で結果を得ます.

漸近解析の理解

例として、t(n)＝n ^ 2＋2 n＋8として得られる時間複雑関数が考えられる.ここで、nの大きな値については、(2 n + 8)はn ^ 2と比較して有意になりません.

また,高次係数の定数項を無視する.250 N ^ 2と300 N ^ 3を持つ場合、N ^ 2とN ^ 3を無視する定数しか考慮しない.

Big‐O複雑性の解析

o ( 1 )

時間の複雑さはO ( 1 )であると言われています.これはループ(入力によって変化する)、再帰、関数呼び出しを含んでいない場合です.

for(int i=0; i < 25; i++){
//statments
}

o ( n )

ループ内の変数をインクリメントしたりデクリメントしたりするとき、時間の複雑さはO(n)であると言われています.

for(int i= n; i > 0; i--){
//statments
}

O ( n ^ k )

時間の複雑さはo(n ^ k)(kは1,2,3…)であると言える回の数だけ入れ子になったループの最内側のループが実行されます.

for(int i= 0; i < n; i++){
for(j= 0 ;j < n; j++){
//statments
  }
}

o ( logn )

ループ変数を分割したり,定数を乗じた場合,時間複雑度はo(logn)と考えられる.

for(int i = 0; i < n; i = i * c){
//statments
}

ビッグオーシート

組み込み関数の時間複雑性を考慮するか？

はい、我々は時間の影響を与える組み込み関数の時間の複雑さを考慮するCollections.sort() javaではマージソートを使い,o(nlogn)の複雑さを持つ.sort() Pythonではtimsortを使い、o ( nlogn )などの複雑さを持ちます.

条件文の時間計算量

//pseudocode
input n
if n<7
print "n is less than 7"
else
for int i = 0 to n
print i

ここで、私たちが与える入力が7未満であるならば、上記のコードを観察してください、そして、時間複雑さがo(1)であるように、我々はprint声明だけを実行します.入力が7より大きいならば、N回のために実行するforループがあります.したがって、複雑さはNです.したがって、最高のケース時間複雑さはO(1)です、そして、最悪のケースはO(N)です.
それです.今、あなたは自分でコードの時間の複雑さを見つけることができます.畝

あなたが好きかもしれない他の記事

・Markdown Cheatsheet to write stunning articles!・

・Mastering this keyword in JAVA・

・Scanner class nextLine() issue resolved in JAVA・

・Adding an SSH key in GitHub・