Python アルゴリズム表現の概念リテラシーに関するチュートリアルの例

この記事は主に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=log<3>9;

② 4^(3/2)=8 <==> 3/2=log<4> 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)

２乗次数O(n^2)

for i in range(100):
 
  for k in range(100):
    print(i,k)

3次次数O(n^3)k乗次数O(n^k)、

指数次数O(2^n)。


問題サイズnが増加し続けると、上記の時間計算量は増加し続け、アルゴリズムの実行効率は低下します。

以上がPython アルゴリズム表現の概念リテラシーに関するチュートリアルの例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。