시간복잡도(Time-Complexity), 빅오표기법(Big-O)

시간복잡도 (Time-Complexity)

복잡도는 시간복잡도와 공간복잡도로 나뉜다.

 

• 시간복잡도
  • 알고리즘에서 주어진 문제를 해결하기 위한 연산 횟수
  • 입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간
    
    • but 시간은 컴퓨터 사양마다 다르므로 로직이 얼마나 반복되었는가 중점으로 측정
  • 일반적으로 데이터 크기가 클 수록 시간 복잡도가 올라간다.
  • 주요 로직의 반복횟수를 중점으로 측정
  • 가장 많이 중첩된 for문이 전체 코드의 시간 복잡도의 기준이 된다.

ex)1~100 사이의 무작윗값을 찾아 출력

Big - Ω  빅-오메가	best case	1
Big - Θ 빅-세타	average case	N/2
Bit - O 빅-오	worst case	N

1000000번 더하는데 1.575ms 걸리네? 하지만 이것은 컴퓨터 사양마다 다르다.

 

시간복잡도 도출 기준

• 상수는 시간 복잡도 계산에서 제외 

연산횟수가 3배차이가 나지만 두 코드의 시간 복잡도는 같다.

연산횟수 = N = 10000

N = 10000
cnt = 1

for i in range(N):
	print("연산 횟수" + str(cnt))
    cnt += 1

연산횟수 = 3N = 30000

N = 10000
cnt = 1

for i in range(N)
	print("연산횟수" + str(cnt))
    cnt+=1
    
for i in range(N)
	print("연산횟수" + str(cnt))
    cnt+=1

for i in range(N)
	print("연산횟수" + str(cnt))
    cnt+=1

• 가장 많이 중첩된 반복문의 수행횟수가 시간 복잡도의 기준이 된다.

연산횟수 = N2^

N = 10000
cnt = 1

for i in range(N):
	for j in range(N):
    	print("연산 횟수" + str(cnt))
        cnt +=1

가장 많이 중첩된 for문이 전체 코드의 시간복잡도가 된다.

---

빅오표기법 (Big O)

빅오표기법

• 복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 뺴고 나머지 항을 없애서 복잡도를 나타내는 표기법
• 알고리즘별 빅-오(worst case) 비교 후 가장 효율적인 것으로 알고리즘을 선택한다(적합성)
•  n! > 2^n  > n^2 > nlogn > n > logn > 1 
  • 상수시간 시간복잡도 O(1) : 입력 크기와 상관없이 일정한 시간복잡도를 가지는 것
    • 입출력: cin,cout,scanf, printf
    • 곱하기, 나누기, 나머지연산, 빼기 등
    • 간단한 비교 if문
    • 배열의 인덱스 참조 등

입력크기n에 따라 증가 속도가 빠른 것, 기울기가 높은 것