자료구조 (Data Structure) 알고리즘(Algorithm), 시간 복잡도

 

📍 자료구조(Data Structure)는 데이터를 저장하고 관리하는 방식이다.

• 수 많은 데이터들을 어떤 자료구조로 저장하느냐에 따라 검색과 같은 알고리즘의 속도가 달라진다.
• 실행시간이 달라질 수 있고, 메모리 공간의 사용량에도 영향을 미친다.

=  따라서, 자료구조와 알고리즘은 실행시간과 메모리 사용량을 고려하여 효율적으로 설계해야 한다.

 

📍 알고리즘(Algorithm)은 어떤 문제를 해결하는 방법을 말한다.

• 전화번호부를 자료구조라고 한다면, 번호를 찾는 방법을 알고리즘이라고 할 수 있다. 
• 전화번호부(자료구조)에 따라 번호를 찾는 방법(알고리즘)이 달라질 수 있다.

---

 

📍 좋은 알고리즘이란, 시간 복잡도 & 공간 복잡도 & 구현 복잡도

• 시간 복잡도: 적은 시간을 잡아먹는 알고리즘일수록 좋다. Big-O의 시간 복잡도를 통해 비교한다.
• 공간 복잡도(메모리): 메모리는 한정적이기 때문에, 최대한 적은 용량의 메모리를 사용하는 것이 좋다. 
• 구현 복잡도: 구현이 너무 복잡하지 않도록 되도록 깔끔한 코드를 작성하는 것이 좋다.

 

💥 시간 복잡도: Running Time(실행시간)

• 코드를 작성하여 프로그램을 실행하면 CPU는 한 줄 한 줄 코드를 처리한다. 이렇게 모든 코드를 실행하는데 걸리는 시간을 runtime이라고 한다. 
• 실행시간에 영향을 주는 요소
  
  • 한 줄의 코드당 걸리는 시간
  • 프로그램 내 실행되는 코드의 갯수
  • ex) CPU 1 tick당 걸리는 시간을 1 unit time이라고 하자. (코드의 종류에 따라 unit time은 달라질 수 있음) 변수에 값을 대입하는 코드는 1 unit time이 걸리지만, 두 변수를 더한 값을 변수에 대입하는 코드는 3 unit time이 걸릴 수 있다. 

 

• runtime(n) = C 

print('hi') # C unit time

 

• runtime(n) = 100 * C1 = C

for i in range(100):
    print('hi') # C1 unit time

 

• runtime(n) = 100 * 100 * C1  + C2 = C

for i in range(100):
    for j in range(100):
        print('hi') # C1 times
        
print('bye') # C2 times

 

• runtime(n) = n * C1 + C2 = An + B

for i in range(n):
    print('hi') # C1 times
print('bye') # C2 times

 

• 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력값 n의 함수 관계를 말한다. 
• 시간 복잡도를 구하는 이유는, 내가 고안해낸 알고리즘으로 작성한 코드가 얼마만큼의 실행시간이 걸릴지 예상하기 위함이다.
• 시간 복잡도는 runtime(n) 값을 토대로 Big-O notation으로 표현한다. 

 

💥 Big-O

• input n의 크기가 커지면 작은 차수의 항들이 runtime에 미치는 영향이 미미하다. → 작은 차수 무시, 계수 무시

 

 

• O(1)

a = 5 
a += 1

• O(n)

for i in range(n):
    print('hi')

 

• O(n^2)

for i in range(n):
    for j in range(n):
        print('hi')

• O(2^n): 두 번 재호출하는 재귀함수 (recursion)

def fibo(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

 

• O(logn): 탐색해야 되는 데이터가 절반씩 줄어드는 함수 (이진 탐색 알고리즘 등)

def binarySearch(data, n, target):
    start = 0
    end = n
    mid = 0
    
    while end >= start:
        mid = (end + start) / 2
        if data[mid] == target:
            return 1
        elif data[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return 0

 

 

 

개발남 노씨의 설명을 참고하여 작성하였습니다.

https://www.nossi.dev/cote/time-complexity