基本スキル探索#1-時間複雑度

時間の複雑さとは?

アルゴリズムの実行速度

重要な要素

複文によって支配される.

いくつかのif文を追加することは重要ではありません.重要なのは、繰り返し文宣言

です.

マーキングほう

BigO(Big-O)記号:O(N)

アルゴリズムの最悪の実行時間は

とマークされている.

最大/最も一般的な

最低性能

n単位でと表記され、

式に最も影響を及ぼす

入力nによって決定される時間複雑度関数

O(1) < O(logn) < O(n) < O(nlogn) < O(n2n^2n2) < O(2n2^n2n) < O(n!) 順位の多い

式の計算方法

O(1)

nの値を考慮することなく、運転定数は

である.

def print_item(something_list, item_num):
	print(something_list[item_num])

時間複雑度O(1)

の複文はなく,時間的複雑度はほぼO(1)

である.
O(n)
nでn回、2 n回、4 n+2回など実行→全てO(n)と表記

def print_double_forloop(n):
	for i in range(n):
		print(i)

	for j in range(n):
		print(j)

O(n2n^2n2)
n,n 2 n^2 n 2回,n 2+100 n^2+100 n 2+100 n 2+100回等により実行→全てO(n 2 n^2 n 2 n 2)と表記する

def print_double_forloop(n):
	for i in range(n):
		for j in range(n):
			print(i * j)

O(lognlognlogn)
nの検出範囲は1回行うごとに半分に減少→O(lognlognlogn)[木を用いたときの観察]

def binsearch(x_list, target):
  min_point, max_point = 0, len(x_list)

  while True:
    if a == b:
      return -1

    center = (a + b) // 2

    if x_list[center] == target:
      return center
    if x_list[c] > target:     # 구간을 왼쪽 절반으로 줄임
      min_point, max_point = min_point, center
    else:             # 구간을 오른쪽 절반으로 줄임
      min_point, max_point = center + 1, max_point

def print_powers_of_two(n):
    i = 1
    while i < n:
        print(i)
        i = i * 2

O(2n)2^n)2n)
O(lognlognlogn)とは逆に,nを1個増加するごとに約2倍増加する.→ O(2n)2^n)2n)

function func (num){
  if(num <= 1){
    return num;
  }else{
    return func(num-1) + func(num-2);
  }
}