강의를 둘러보던 도중, 핸드북 보면서 가끔 나왔던 O(n)이런 구문이나왔다.
프로그래머스 코딩문제에도 시간관련해서 무엇인가 눈에 밟히는 부분이 있어서
정리하면서 짚고 넘어가면좋겠다 싶었는데, 잠깐의 검색만으로는 이해할 부분이 아니라고판단,
한번정도 정의한후 인지만 하고 넘어가겠다. 나중에 다시 개념을 쌓아야 될부분이기때문에
공간자원과 공간복잡도
- 공간자원(space resource) : 프로그램이 실행될 때 필요한 메모리 양.
변수, 자료구조, 함수 호출 스택 등 프로그램이 실행되면서 사용하는 모든 메모리 공간을 포함
- 공간복잡도(space complexity) : 알고리즘이 실행되는 동안 필요한 총 메모리 공간의 양으로, 입력 크기의 함수로 표현.
시간자원과 시간복잡도
- 시간자원(time resource) : 프로그램이 작업을 완료하는 데 걸리는 실제 시간.
이는 프로세서의 속도, 메모리 속도, 입출력 속도 등 많은 요소에 의해 영향을 받음
- 시간복잡도(time complexity) : 알고리즘이 문제를 해결하는 데 필요한 단계의 수로, 입력 크기의 함수로 표현. 시간복잡도는 알고리즘의 효율성을 평가하는 주요 지표 중 하나
빅 오 표기법?
알고리즘의 성능을 나타내기 위해 사용되는 수학적 표현 O(n)으로, 알고리즘의 실행 시간이나
필요한 메모리 공간이 입력 크기에 따라 어떻게 증가하는지를 나타내는 상한선을 제공.
주로 최악의 경우를 고려하여 알고리즘의 효율성을 평가하는 데 사용됨.
- O(1) : 상수 시간 및 공간
알고리즘이 입력 크기와 무관하게 일정한 시간과 공간을 사용하는 경우.
예를 들어, 배열에서 특정 위치의 요소에 접근하거나 하나의 정수 변수에 최대값을 저장하는 경우.
이러한 연산은 입력 데이터의 크기나 개수에 영향을 받지 않으므로, 시간 복잡도와 공간 복잡도 모두 O(1).
- O(log n) : 로그 시간 및 공간
입력 크기가 커질수록, 알고리즘의 수행 시간이나 필요한 공간이 로그 함수적으로 증가.
이진 탐색은 대표적인 O(log n) 시간 복잡도를 가진 알고리즘으로, 데이터를 반으로 나누어 탐색하기 때문에, 시간 복잡도가 로그에 비례.
공간 복잡도 측면에서도, 재귀 호출을 사용하는 경우 호출 스택의 깊이가 로그에 비례하여 증가.
- O(n) : 선형 시간 및 공간
알고리즘이 입력 데이터의 크기에 비례하여 시간이나 공간을 사용하는 경우.
예를 들어, 배열을 순회하거나 입력 배열의 복사본을 생성하는 경우가 이에 해당.
이 경우, 입력 데이터의 개수가 n일 때, 알고리즘의 실행 시간이나 필요한 공간도 n에 비례하여 증가.
- O(n log n) : 선형 로그 시간 및 공간
특정 정렬 알고리즘들(예: 병합 정렬)이 이 범주에 속함.
이러한 알고리즘들은 데이터를 분할하고, 각 부분을 정렬한 뒤 병합하는 과정에서 n log n의 시간과 공간을 필요.
- O(n^2) : 제곱 시간 및 공간
간단한 정렬 알고리즘(예: 버블 정렬, 선택 정렬)이나 행렬 곱셈 같은 연산에서 볼 수 있는 복잡도.
이는 입력 데이터의 크기 n에 대해, 시간이나 공간이 n의 제곱에 비례하여 증가.
- O(2^n) : 지수 시간 및 공간
모든 부분 집합을 생성하는 경우.
n개의 요소로 이루어진 집합의 모든 부분 집합의 수는 2^n개이며, 이 경우, 알고리즘의 실행 시간이나 필요한 공간이 입력 크기의 지수 함수적으로 증가
모든 부분 집합을 생성하거나, 결정 문제를 해결하기 위해 가능한 모든 경우의 수를 탐색하는
브루트포스 알고리즘, 피보나치 수열을 재귀적으로 계산하는 알고리즘이 이에 해당
- O(n!): 팩토리얼 시간 및 공간
모든 순열을 생성하는 경우. n개의 요소로 가능한 모든 순서의 배열을 생성하면,
총 n!개의 순서가 존재하며, 이를 저장하기 위해서는n!만큼 팩토리얼 크기의 공간과 시간이 필요.
이는 매우 드문 경우이며, 일반적으로 매우 비효율적.
ex) 모든 가능한 순서로 요소를 나열하는 브루트 포스(완전 탐색) 방식의 알고리즘
중요한 이유
일반적으로 알고리즘을 설계하고 선택할 때는 낮은 시간 복잡도와 공간 복잡도를 가지는 것이 좋음.
다만 시간복잡도와 공간복잡도는 서로 반비례 하기 때문에 문제의 요구 사항과 사용 가능한 자원에 따라 적절한 균형을 찾는게 중요함.
엉덩이가 무거운 사람