整理時間の複雑さ

コード1とコード2はいずれも1からNまでの和を求めるコードである.
2つのコードのうち、どちらが時間的に有効ですか?
Code 1

#첫번째 코드
sum1 = 0
for i in range(1,N+1):
sum1+=i

Code 2

#두번째 코드
sum1 = (N+1)*N/2

答えは2番目のコードです.

時間の複雑さとは?

時間複雑度は,計算された数と実行された演算数によって論理の効率を解析する.

時間複雑度の種類

最適:ω記号

の平均値:3打法(Big-θ Notation)

最悪の場合:大文字

3つのマーキング法があります.
Θ 計算記号は最も理想的であるが、計算は複雑であり、通常big−o記号を用いて時間複雑度を表す.
原因:Big-Oマーキング法は最大差港湾をマーキングするだけで、使いやすく、アルゴリズムが最悪の場合、平均に近い結果を予測できる.
##Big-O記号
bigoマーキング法は,不要な演算を除去し,アルゴリズム解析を容易にするために用いられる.
大きなOの複雑さを測るには時間と空間の複雑さがある.
時間複雑度は、入力Nの大きさに応じて実行されるオペランドを表す.
スペースの複雑さは、アルゴリズムの実行時に使用されるメモリの量を表します.
現在、データを格納するメモリの発展は、その重要性を低下させています.
代表的なBig−O複雑度の表を以下に示す.

計算時間の複雑さ

コード1とコード2の時間的複雑さを計算します.
Code 1

#첫번째 코드
sum = 0
for i in range(1,N+1):
sum+=i

まず、最初のコードは
sum=0 1回
一次int i=1
i++このN回
sum+=iはN番です
合計2 N+2演算を実行した.
Big−Oで表すと2 N+2=O(N)であるため,最初のコードの時間的複雑度はO(N)である.
Code 2

#두번째 코드
  sum = (N+1)*N/2

2番目のコードは
(N+1)今回
*N一回
/2街に一度
代入演算は1回マージされ、合計4回の演算が実行されます.
Big−O記号で表すと4=O(1)であるため,2番目のコードの時間的複雑度はO(1)である.

とにかく...

O(N)>O(1)であるため,2番目のコードは1番目のコードよりも時間的に有効である.


Nが1のときはほとんど差がありません
時間が経つにつれて、格差はますます大きくなってきた.

O(1):定数

# 입력에 관계 없을 떄

def hello_world():
      print("hello, world!")

O(N):線形

#입력이 증가하면 시간과 공간 복잡도가 선형적으로 증가 

def print_each(li):
  for item in li:
      print(item)

O(N^2) : Square

#반복문이 2번일 때

def print_each_n_times(li):
  for n in li:
      for m in li:
          print(n,m)

O(log n) O(n log n)

#

def binary_search(li, item, first=0, last=None):
	if not last:
		last = len(li)

	midpoint = (last - first) / 2 + first

	if li[midpoint] == item:
		return midpoint

	elif li[midpoint] > item:
		return binary_search(li, item, first, midpoint)

	else:
		return binary_search(li, item, midpoint, last)

O(2^n)

# 급격하게 복잡도가 증가한다
# 피보나치 수열이 그 예
void fibonacci(int n, int r){
  if (n<=0)
  	return 0;
  else if (n==1)
  	return r[n] = 1;
  return r[n] = fibonacci(n-1,r) + fibonacci(n-2,r)

ソース

https://roytravel.tistory.com/34
https://dbstndi6316.tistory.com/233
https://blog.chulgil.me/algorithm/
https://medium.com/humanscape-tech/%EC%BD%94%EB%93%9C%EC%9D%98-%EC%8 B%9 C%EA%B 0%84-%EB%B 3%EC%9 E%A 1%EB%8 F%84-%EA%B 3%84%EC%B%82%B%ED%95%EA%B 8%B 8%B 8%B 0-b 67 dd 8625966**テキスト**