この記事は主にPythonアルゴリズム表現の概念リテラシーチュートリアルを詳しく紹介していますので、興味のある方は参考にしてください。
具体的な内容は次のとおりです。以下の通り
定数次数O(1)
定数とは値が変わらない定数のことを指します
なぜ次のアルゴリズムの時間計算量は変化しないのか。 O(3)ですが、O(1)です。
int sum = 0,n = 100; /*执行一次*/ sum = (1+n)*n/2; /*执行一次*/ printf("%d", sum); /*行次*/
このアルゴリズムの実行回数関数は f(n)=3 です。 big O 次数を導出する私たちの方法によると、最初のステップは定数項 3 を 1 に変更することです。最上位項を保持すると、最上位項がまったくないことがわかり、このアルゴリズムの時間計算量は O(1) になります。
さらに、このアルゴリズムのステートメント sum=(1+n)*n/2 に 10 文があると想像してみましょう。つまり:
int sum = 0, n = 100; /*执行1次*/ sum = (1+n)*n/2; /*执行第1次*/ sum = (1+n)*n/2; /*执行第2次*/ sum = (1+n)*n/2; /*执行第3次*/ sum = (1+n)*n/2; /*执行第4次*/ sum = (1+n)*n/2; /*执行第5次*/ sum = (1+n)*n/2; /*执行第6次*/ sum = (1+n)*n/2; /*执行第7次*/ sum = (1+n)*n/2; /*执行第8次*/ sum = (1+n)*n/2; /*执行第9次*/ sum = (1+n)*n/2; /*执行第10次*/ printf("%d",sum); /*执行1次*/
実際、n が何であっても、上記の 2 つのコードはは 3 倍の合計です。 12 回の実行の差です。このアルゴリズムは、問題の大きさ(n の大きさ)に関係なく実行時間が一定であるため、時間計算量 O(1) と呼ばれ、定数次数とも呼ばれます。
注: この定数がどのようなものであっても、O(3)、O(12) などの他の数値ではなく、O(1) として記録します。これは初心者がよく犯す間違いです。
Big O 順序メソッドの導出
1. 実行時のすべての加法定数を定数 1 に置き換えます
2。最高位項が存在し、1 でない場合は、この項に乗じた定数を削除します
対数次数 O(log2n)
対数 a の x 乗が N に等しい場合 (a> ;0、および a が 1 に等しくありません)の場合、数値 x は a を底とする N の対数(対数)と呼ばれ、x=logaN、と記録されます。このうち、aは対数の底、Nは実数と呼ばれます。
5^2 = 25、2= log5 25 として記録されます対数は演算であり、指数関数との逆数演算です。たとえば、
① 3^2=9 2=log9;
② 4^(3/2)=8 3/2=log 8 ;
③ 10^n=35 n=lg35。使いやすくするために、人々は底が 10 の常用対数を lgN として徐々に記録します
対数次数int count = 1;
while (count < n)
{
count = count * 2; /* 时间复杂度为O(1)的程序步骤序列 */
}
カウントが 2 倍になるたびに、n に 1 ポイントずつ近づくためです。
つまり、2 を掛け合わせた数が n より大きい場合、ループは終了します。
2^x=n から、x=log2n が得られます。したがって、このループの時間計算量は O(logn) です。
線形次数O(n)問題サイズに比例して実行時間は増加する
data = [ 8,3,67,77,78,22,6,3,88,21,2] find_num = 22 for i in data: if i == 22: print("find",find_num,i )対数線形次数O(nlog2n)
2乗次数O(n^2)for i in range(100):
for k in range(100):
print(i,k)
3次次数O(n^3)
指数次数O(2^n)。
問題サイズnが増加し続けると、上記の時間計算量は増加し続け、アルゴリズムの実行効率は低下します。
以上がPython アルゴリズム表現の概念リテラシーに関するチュートリアルの例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。