복잡도(Big-O ,시간, 공간)

복잡도란?

• 알고리즘의 성능 , 효율성을 나타내는 척도
• 크게 시간 복잡도와 공간 복잡도로 나눌 수 있다.
• 각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준
• 복잡도를 나타내는 방법 점근 표기법으로 빅오, 오메가 ,세타 등

-> 즉 ,어떤 알고리즘이 효율적인지를 판단하는 척도

 

수행시간 -> 시간 복잡도, 메모리 사용량 -> 공간 복잡도

 

---

시간 복잡도(Time Complexity)

• 알고리즘을 실행하여 종료할때까지 필요한 시간 (얼마나 빠른지)
• 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수

이름은 시간 복잡도이지만 실행시간이 아닌 연산 횟수를 세는 이유는

1. 모든 OS, IDE, 플랫폼에서 동일한 결과가 나오지 않음.
2. 실행 시간 측정을 위한 또다른 방법이 필요.

 

알고리즘의 성능 평가

1. 최선의 경우(Best Case)
   • 가장 연산 횟수가 적음 (오메가)
2. 최악의 경우(Worst Case) :
   • 가장 연산 횟수가 많음 (빅오 표기법)
3. 평균의 경우(Average Case) 
   • 총 연산 횟수를 계산하고 시행 횟수로 나눈 경우 (세타 표기법) 
   • 가장 정확해서 좋지만 평가하기 까다로움

-> 평균의 경우와 최악의 경우가 많이 활용, 복잡해지면 최악의 경우

 

공간복잡도(Space Complexity)

• 프로그램을 실행시킨 후 완료하는데 필요로 하는 자원 공간의 양
  -> 즉, 알고리즘이 필요로 하는 "메모리의 양"을 의미

주어진 알고리즘을 실행시키기 위해 필요한 기억장치는 다음과 같이 두가지

1. 알고리즘과 무관한 공간, 즉 고정 공간
   -> 코드가 저장되는 공간, 알고리즘 실행을 위해 시스템이 필요로 하는 공간
2. 알고리즘과 밀접한 공간, 즉 가변 공간
   -> 문제를 해결하기 위해 알고리즘이 필요로 하는 공간. 변수를 저장하는 공간, 순환 프로그램일 경우 순환 스택 등
   (배열, 재귀호출)

알고리즘 성능을 판단 할 때는 시간 복잡도를 위주로 판단

 

빅오 표기법

• 복잡도를 나타내는 점근 표기법 중 가장 많이 사용되는 표기법
• 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용
• 최악의 경우를 고려하는데 가장 좋은 표기법( 알고리즘 효율성은 값이 클수록, 즉 그래프가 위로 향할수록 비효율적)

 

특징 1. 상수항 무시

• 빅오 표기법은 n이 충분히 크다고 가정하고 있고, 알고리즘 효율성은 n의 크기에 영향을 받으므로 무시
  -> O(2n) 은 O(n)으로 간주

1. 영향력 없는 항 무시

• 빅오 표기법은 n의 크기에 영향을 받으므로 가장 영향력이 큰 항 이외에 영향력이 없는 항은 무시
  -> O(n^2 + 2n +1 )은 O(n^2)으로 간주

 

O(1) < O(log n) < O(n) < O(n * log n) < O(n²) < O(n³) < O(2^n) < O(n!)

 

---

💠공간 복잡도 계산법

 

1차원 배열을 만들면 O(n)의 공간 필요
2차원 배열을 만들면 O(n^2)의 공간 필요

1                O(1) --> 상수
2n + 20    O(n) --> n이 가장 큰영향을 미친다.
3n^2         O(n^2) --> n^2이 가장 큰영향을 미친다.

 

 

O(1) : 상수 시간

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

 

입력 자료의 수(N)과 상관없이 언제나 일정한 실행 시간을 갖는 알고리즘

 

O(N): 선형 시간
N번의 반복문

 

O(N^2) : 2차 시간
이중 for문,삽입정렬,,

 

O(logn) : 로그시간
이진 검색, 퀵 정렬, 병합 정렬, 힙 정렬

 

💠시간 복잡도 계산법

def mul(n):
	return n*n

곱셈 연산 1개 사용 O(1)

 

def mul(n):
	sum = 0
    for i in range(n):
   		sum += n

1차원 배열 공간복잡도 O(n)
곱셈 연산 n번 실행 -> O(n)

 

def mul(n):
	for i in range(n):
    		:
    	for j in range(n):
        		:

2차원 배열 공간복잡도 O(n^2)

 

 

 

🚩시간 복잡도를 구하는 요령

• 하나의 루프를 사용하여 단일 요소 집합을 반복하는 경우: O(n)
• 컬렉션의 절반 이상을 반복하는 경우: O(n / 2) -> O(n)
• 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복하는 경우: O(n + m) -> O(n)
• 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우: O(n²)
• 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복하는 경우: O(n * m) -> O(n²)
• 컬렉션 정렬을 사용하는 경우: O(n*log(n))

 

+버블정렬은 시간 복잡도 O(n^2) , 공간복잡도 O(n)