Hello New World
Categories Posts Tags
Hello New World

Contents

Time Complexity 시간복잡도

 included in Computer Science 시간복잡도
   1094 words   6 minutes 

​

Time Complexity (시간 복잡도)

효율적인 알고리즘 구성을 위해 항상 신경써야하는 시간 복잡도.

그리고 시간 복잡도를 표기하는 방법인 Big-O(빅-오) 표기법에 대해 정리합니다.

​

​

시간 복잡도

  • 위키백과에 따르면 시간복잡도는 계산복잡도 이론에서 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 또
  • 컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것인데,
  • 간단히 input 후 연산이 진행되고 output을 반환하는데 시간이 얼마나 걸리는가?를 계산한 값입니다.
  • 조금 더 간단하게는 알고리즘의 수행시간입니다.

​

위에서 계산한 값이라고 적었는데 이 계산한 값의 표기법 중 하나가 Big-O(빅-오) 표기법입니다.

​

​

Big-O 표기법

시간복잡도 표기법에는 3가지 방법이 있습니다.

  • Big-O(빅-오) ▶️ 알고리즘이 수행되는데 최악의 시간으로 결과값이 반환되는 경우 (상한 *점근)
  • Big-Ω(빅-오메가) ▶️ 알고리즘이 수행되는데 최선의 시간으로 결과값이 반환되는 경우 (하한 점근)
  • Big-θ(빅-세타) ▶️ 그 둘의 평균

위 세가지 경우 중 주로 Big-O(빅-오) 표기법으로 수행 시간을 고려하는 것이 좋습니다.

최악을 대비하는 것이 더 바람직하기 때문입니다.

​

점근: 점점 가까워 지는 모양 ? 점근 표기법: 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법.

​

​

​

Big-O 표기법의 특징

  1. 상수항 무시

    빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다.

    ex) O(2N) ▶ O(N)

  2. 영향력 없는 항 무시

    빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들은 무시한다.

    ex) O(N^2 + 2N + 1) ▶ O(N^2)

​

​

Big-O 표기법의 종류

  1. O(1)

  2. O(log n)

  3. O(n)

  4. O(n * log n)

  5. O(n^2)

  6. O(n^n)

    ​

그래프로 보면 성능의 비교가 가능한데

  • FAST : O(1) — O(log n) — O(n) — O(n * log n) — O(n^2) — O(n^n) SLOW
  • FAST : 상수함수 - 로그함수 - 선형함수 - 로그 함수와 선형 함수의 곱 - 다항함수 - 지수함수 : SLOW
  • (오른쪽으로 갈 수록 속도가 느려진다.)

​

​

O(1)

O(1)는 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.

입력값의 크기와 관계없이, 즉시 출력값을 반환하는 알고리즘을 의미한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

## example 1
def hello_world():
    return print("hello_world")

## example 2
def O1_algo(list, index):
    return print(li[index])

li = [1,2,3,4,5,6]
idx = 1
O1_algo(li, idx) # li의 길이가 아무리 길어도 idx가 1로 고정임으로 항상, 즉시 출력값을 얻을 수 있다.

​

​

​

O(log n)

O(log n)은 로그 복잡도(logarithmic complexity)라고 부르며, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

log n은 보통 log의 밑이 2인 경우를 상정합니다. == $\log_{2}{n}$

이는 *이진탐색의 로직과 거의 유사합니다. 예를 들어서 이야기 해보죠.

  • 8개의 값이 주어졌을 때 이진 탐색으로 내가 원하는 값을 찾는 방법입니다.

    • 8 > 4 > 2 > 1 총 3번의 탐색이 필요합니다. (운이 좋으면 1번에 찾을 수도 있지만, 최악의 상황을 가정)

    • $8 = 1 \times2^3$

  • 만약 주어진 데이터가 N개고, X번의 탐색으로 통해 1이 되는 경우를 공식화하면

    • $N = 1 \times2^X$
    • 몇 번의 과정을 거쳐야 하는지 즉, 효율을 계산하려면 $X$가 필요하고 이를 구하기 위해 양변에 $\log_{2}$를 취하면

  • $X = \log_{2}{N}$

자연스럽게 log n의 식이 도출되고 이것이 O(log n) 복잡도입니다.

​

💡여기서 잠깐,
  • 배열의 크기가 3일 때 이진 검색은 2단계
  • 배열의 크기가 7일 때 이진 검색은 3단계
  • 배열의 크기가 15일 때 이진 검색은 4단계
  • 배열의 크기가 100일때 이진 검색은 7단계
  • 배열의 크기가 10,000일때 이진 검색은 13단계
  • 배열의 크기가 1,000,000일때 이진 검색은 20단계

👉 데이터가 커질수록 단계 수가 늘어나므로 이진 검색은 O(1)이라 표현할 수 없습니다.

👉 검색하고 있는 배열의 원소 수보다 단계 수가 훨씬 적으므로 O(N)이라 표현할 수도 없습니다.

​

O(log n)은 O(1)과 O(N) 사이 어디쯤엔가 있다.

저는 간단히 1/2 연산을 몇번 해야 되는지 알려주는 값이라고 외우고 있습니다.

또는 데이터가 두 배로 증가하면 한 단계씩 늘어나는 알고리즘

​

이진탐색: 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복

​

​

​

O(n)

O(n)은 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.

데이터가 늘어날 때 정확히 그 데이터에 비례해 단계 수가 증가하는 알고리즘이다.

1
2
3
4
5
6

## example  -  li의 길이에 따라 단계 수가 증가
def On_algo(li):
    for i in li:
        return print(i)
    
li = [1,2,3,4,5,6,7,8,9,10]

​

​

​

O(n * log n)

일반적으로 최적화된 알고리즘의 경우 해당 시간복잡도를 가진다.

linear한 단일 컬렉션에 logarithmic한 수행을 반영한 알고리즘이다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

## example  -  퀵 정렬(Quick Sort)
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

# 예시 리스트
example_list = [38, 27, 43, 3, 9, 82, 10]

# 퀵 정렬 수행
sorted_list = quick_sort(example_list)

print("정렬 전:", example_list)
print("정렬 후:", sorted_list)

​

​

​

O(n^2)

O(n^2)은 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n^2)라고 표현한다.

1
2
3
4
5

## example 1
def O_quadratic():
    for i in range(1, 100):
        for j in range(1, 100):
            return print(i, j)

간단히 2중 중복문의 경우에 해당합니다.

3중, 10중 중복문의 경우에도 O(n^2)라고 표현합니다.

​

​

​

O(2^n)

O(2^n)은 기하급수적 복잡도(exponential complexity)라고 부르며, Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.

대표적인 예가 피노나치의 수열인데,

피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열입니다.

  • [1, 1, 2, 3, 5, 8, ….]
1
2
3
4

def fibonacci(n):
    if n <= 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

많은 기술 블로그들이 이렇게 코드 짤꺼면 그냥 하지마라. 고 말하곤 합니다.ㅎ

​

​

​

복잡도 정량화 비교

Complexity 1 10 100
O(1) 1 1 1
O(log n) 0 2 5
O(n) 1 10 100
O(n log n) 0 20 461
O(n^2) 1 100 10000
O(2^n) 1 1024 1267650600228229401496703205376

​

​

​

​

시간 복잡도를 구하는 요령

  • 하나의 루프를 사용하여 단일 *컬렉션을 반복하는 경우: O(n)
  • 두 개의 다른 루프를 사용하여(중첩 X) 두 개의 다른 컬렉션을 반복하는 경우: O(n) + O(m) => O(n)
  • 두 개의 중첩 루프를 사용하여 단일 컬렌션을 반복하는 경우: O(n^2)
  • 두 개의 중첩 루프를 사용하여 두 개의 다른 컬렉션을 반복하는 경우: O(n) * O(m) => O(n^2)

컬렉션 자료형: 여러가지 요소를 하나로 묶어 사용하는 데이터 타입. python의 경우 시퀀스(리스트, 튜플, 딕셔너리, 레인지), 매핑(딕셔너리), 집합 등이 있다.

​

​

​

​

​

​

​

​

​

👀 마치면서..

사실 이론은 복잡하지 않습니다.

이 정리를 통해 어느 정도 이해할 수 있었다면, 실제 개발에서 효율을 고려하며 개발한다.를 적용할 수 있도록

코드마다 시간복잡도를 생각하면서 개발하는 노력이 필요할 것 같습니다.

​

​

​

​

​

Updated on 2023-10-17
Read Markdown
 CS, 시간복잡도, computer science, 면접대비
Back | Home