복잡도란?

알고리즘의 성능을 나타내는 척도

복잡도는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있다.

시간 복잡도

시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지, 얼마만큼의 연산이 필요한지를 의미한다.

시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용하는데, 최고차 항만 고려하는 표기법이다.

Big-O 표기법 (아래로 갈수록 느림)

• O(1) 상수 시간(Constant time) : 문제를 해결하는데 오직 한 단계 처리
  
  

int a = 1;
int b = 2;

System.out.println(a+b);  // 3

위 소스코드의 연산 횟수는 1회이다. 더하기 연산 1 번이 수행되기 때문에 이는 상수 연산이므로 시간 복잡도는 O(1)로 표현할 수 있다. 또한 아래와 같은 경우도 1회 연산된다.

• 1. type 함수 경우 데이터 타입 리턴 (type(A) -> 'int')
• 2. len 함수 경우 길이 리턴 (len(list))
• 3. append 함수 경우 리스트 끝에 값 추가 (append(-1))
     
     
     
     

• O(logN) 로그 시간(Log time) :
  문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦
  
  

# 2의 거듭제곱을 출력하는 함수이다.
# 인풋이 리스트가 아닌 단순 정수이다.
def print_powers_of_two(n):
	i = 1
    	while i < n:
        	print(i)
            i = i * 2

• 1. 바이너리 검색
• 2. 이진 검색 트리에서 최대 / 최소 찾기
• 3. 선형 기능을 기반으로 하는 특정 분할 및 정복 알고리즘

  
  
  
  

• O(N) 선형 시간 : 문제를 해결하기 위한 입력 N 만큼 단계가 필요
  
  
  

int[] array = {3, 5, 2, 1, 4};
int sum = 0;

for(int i = 0; i < array.length; i++) {
   sum += array[i];
}

System.out.println(sum);

위 소스코드와 같이 array가 커짐에 따라 비례하여 연산을 수행하는 루프문 부분이므로 시간 복잡도는 O(N)으로 표현할 수 있다.

• 1. 배열 탐색
• 2. 연결된 목록 탐색
• 3. 선형 검색
• 4. 링크 된 목록의 특정 요소 삭제 (정렬되지 않음)
• 5. 두 문자열 비교
• 6. Palindrome 확인하기
• 7. 카운팅 / 버킷 정렬

-> 선형성을 필요로하는 모든 브루트포스 알고리즘은 O(N) 시간 복잡도를 기반으로 한다.

• O(NlogN) 로그 선형 시간 : 문제를 해결하기 위한 단계의 수가 N번에 그 하나의 N번당 단계들이 연산마다 특정 요인에 의해 줄어듦

def print_powers_of_two_repeated(y):
	for i in range(n): # 반복횟수: n에 비례
    	j = 1
        while j < n:   # 반복횟수 : log n에 비례
        	print(i , j)
            	j = j * 2    

합병 정렬, 퀵 정렬을 예로 들 수 있다. 합병정렬의 분할 단계에서 분할되는 깊이가 logN에 비례한다. 각 깊이별로 분할이 수행되어 합병해야 되는 배열의 수는 많아지지만, 총 원소의 수는 N개로 똑같다.

따라서, 각 깊이별로 수행되는 merge의 시간복잡도는 O(N)이 되며, 이것을 모든 깊이에 대해(logN개만큼) 수행하기 때문에 시간 복잡도는 O(NlogN)으로 표현할 수 있다.

• 1. 병합 정렬
• 2. 힙 정렬
• 3. 빠른 정렬

• O(N^2) 이차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 N의 제곱
  
  

int[] array = {3, 5, 2, 1, 4};

for(int i = 0; i < array.length; i++) {
   for(int j = 0; j < array.length; j++) {
      System.out.println(a+b);
   }
}

위 소스코드와 같이 array 크기만큼 중첩루프를 사용하여 연산 수행하므로 시간 복잡도는 O(N^2)으로 표현할 수 있다.

• 1. 버블 정렬
• 2. 삽입 정렬
• 3. 선택 정렬
• 4. 간단한 2D 배열 탐색

-> 이 객체들은 O (nlogn) 대응 객체가있을 경우 덜 효율적인 알고리즘으로 간주된다.

• O(2^N) 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 2의 N제곱
  
  
  
  
  
  대표적으로 피보나치 수열을 예로 들 수 있다. 재귀가 역기능을 할 경우 해당 되며, 데이터량이 많아질수록 처리시간이 기하급수적으로 증가한다.
  
  
  
  
  
  
  
  
  
  참고 : https://velog.io/@ggyungjun0913/%EC%A3%BC%EC%9A%94-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EC%A0%95%EB%A6%AC
  

https://velog.io/@soyeon207/%EB%B3%B5%EC%9E%A1%EB%8F%84-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%B5%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

https://chanos.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98%EC%97%B4%EC%9D%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EC%99%84%EB%B2%BD%ED%9E%88-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0