[React/리액트] 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)

🌏 알고리즘의 성능 분석

 

시간복잡도와 공간복잡도는 알고리즘 성능 평가를 위한 척도로 사용되고 있습니다.

• 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
• 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

그렇다면 알고리즘의 성능 분석은 왜 필요한가? 

프로그램의 규모가 방대해질수록 처리해야하는 데이터의 양이 많아지고, 양이 많아질수록 알고리즘 간의 효율성을 따질 수 밖에 없다.

알고리즘의 수행능력에 따라 연산하는 컴퓨터 내의 메모리와 같은 자원을 효율적으로 사용할 수 있어야 한다.

 

🌏 시간 복잡도

시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 

알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을 수행하는데 연산들이 몇 번 이루어지는 지를 숫자로 표기합니다.

 

🌏 빅오 표기법

빅오 표기법(Big-Oh ontatiojn)이란, 시간 복잡도 함수에서 사용되는 개념으로 상대적으로 불필요한 연산을 제거하여 알고리즘의 분석을 좀 더 간편하게 할 목적으로 시간 복잡도를 표기하는 방법이다.

O1 < O(log N) < O(n) < O(N log N) < O(N^2) < O(2^N) 순으로 효율성이 떨어집니다.

 

[1] O1 : Constant Time(상수 시간)

: 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘. 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않습니다.

** 예) stack의 push, Pop

[2] O(log N) : Logarithmic Time(로그 시간)

: 입력 데이터의 크기가 커질수록 처리 시간이 로그만큼 짧아지는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 됩니다.

** 예) 이진트리

 

[3] O(n) : Linear(선형 시간)

: 입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 됩니다.

** 예) for문

 

[4] O(N log N) : Linear- Logarithmic(선형 로그 시간)

: 데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘. 예를 들어 데이터가 10배가 되면 처리시간은 약 20배가 됩니다.

** 예) quick sort, mertge sort, heap sort

 

[5] O(N^2) : Quadratic(2차 시간)

: 데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 됩니다.

** 예) 이중 for문, insertion sort, bubble sort, selection sort

 

[6] O(2^N) : Exponential(지수 시간)

: 데이터가 많아지수록 처리시간이 기하급수적으로 늘어나는 알고리즘. 데이터의 크기에 따라 처리 시간도 2^N이 됩니다.

** 예) 피보나치 수열

 

🌏 공간 복잡도

공간 복잡도는 프로그램을 실행시킨 후 완료하는데 필요로 하는 자원 공간의 양을 의미합니다.

총 공간요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있으며 수식으로는 S(P) = c + Sp(n)으로 표기합니다.

예전에 비해 컴퓨터 성능의 발달로 메모리 공간의 여유로 인해 중요도는 많이 떨어졌다고 합니다.

 

[1] 공간 복잡도를 줄이는 방법

: 보통 배열의 크기가 몇인지, 얼마 만큼의 동적 할당인지, 몇 번의 호출을 하는 재귀 함수인지 들이 공간 복잡도에 영향을 끼칩니다.

프로그램에 필요한 공간은 크게

• 고정 공간
• 가변 공간

이 있는데, 시간적인 측면을 무시하고 공간 복잡도만 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료 구조가 더 효율적입니다. 함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요합니다.

 

🌏 정리

1. 시간 복잡도는 "얼마나 빠르게 실행되는가?", 공간 복잡도는 "얼마나 많은 자원을 필요로 하는가?"

2. 좋은 알고리즘이란, 실행 시간은 적게, 자원의 사용도 최소한으로 하는것을 의미합니다.

3. 이 과정에서 실행 시간을 표기하는 방법으로서 빅오표기법이 사용되며 6가지의 척도가 존재합니다.

4. 요즘에 들어서는 컴퓨터 기능향상으로 인해 시간 복잡도를 위주로 좋은 알고리즘을 계획하며, 공간 복잡도는 어느정도 감안합니다.

 

 

---

References

References

https://holika.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%B9%85%EC%98%A4-%ED%91%9C%EA%B8%B0%EB%B2%95Big-O-notation%EC%9D%B4%EB%9E%80

[자료구조] 빅오 표기법(Big-O notation)이란?

 

https://velog.io/@cha-suyeon/Algorithm-%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

[Algorithm] 시간 복잡도, 공간 복잡도

https://yoongrammer.tistory.com/79

시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)