자료구조(Data Stucture): 데이터를 저장하고 관리하는 방법을 정의한 구조. 자료를 저장하는 방식에 따라 데이터를 검색, 삽입, 삭제하는 속도나 메모리 효율성이 달라지므로 적절한 자료구조를 선택하는 것이 중요함.(예시: 배열, 연결 리스트, 스택, 큐, 트리, 그래프 등)
알고리즘(Algorithm): 특정 문제를 해결하기 위한 절차나 방법을 단계별로 기술한 것. 어떤 문제를 해결할 때 가능한 가장 효율적인 방법을 찾는 것이 목표임. 알고리즘의 효율성은 수행 시간(시간 복잡도)과 사용 메모리(공간 복잡도)로 측정할 수 있음. (예시: 정렬 알고리즘(버블 정렬, 병합 정렬 등), 탐색 알고리즘(이진 탐색 등), 그래프 탐색 알고리즘(DFS, BFS) 등)
알고리즘 성능: 가상컴퓨터(virtual machine)+가상언어(pseudo language)+가상코드(pseudo code)
자료구조와 알고리즘의 성능: 자료구조와 알고리즘을 통해 다양한 프로그래밍 언어로 작성된 코드가 컴퓨터에서 실행됨. 이 과정에서 하드웨어와 소프트웨어의 제한성이 고려됨.
알고리즘의 시간 복잡도(time complexity): 알고리즘이 실행되는데 걸리는 시간을 입력크기 n에 대한 함수로 표현한 것. 이는 알고리즘의 성능을 평가하는 중요한 기중 중 하나로, 입력 데이터의 크기가 커질 때 알고리즘의 실행 시간이 어떻게 변하는지 나타냄.
알고리즘 수행 시간: 일반적으로 최학의 입력에 대한 기본 연산 횟수로 정의됨. 이는 알고리즘이 처리할 수 있는 가장 어려운 상황(최악의 경우)에 대해 얼마나 많은 기본 연산이 필요한지를 측정한 방식.
왜 최악의 경우를 기준으로 하는가?
- 안전성 보장: 최악의 경우 성능을 분석하면, 알고리즘이 어떤 상황에서도 허용할 수 없는 수준으로 느려지지 않는다는 것을 보장할 수 있음. 이는 알고리즘이 예외적인 상황에서도 일정한 성능을 유지하게 하는데 중요함.
- 예측 가능성: 최악의 경우에 대한 분석은 모든 입력 상황에서 발생할 수 있는 최대 시간을 예측하게 해주며, 프로그램이나 시스템이 예상치 못한 지연 없이 작동하도록 도움.
- 일반적인 평가 기준: 최악의 경우 시간 복잡도를 이용하면 알고리즘 간 성능 비교가 쉬움. 이를 통해 다양한 알고리즘을 공통 기준으로 평가할 수 있으며, 가장 효율적인 알고리즘을 선택하는데 도움이 됨.
시간 복잡도와 빅오 표기법: 시간 복잡도는 주로 빅오 표기범 O-notation을 사용해 표현하며, 최악의 경우 성능을 나타냄.
유형
- 상수 시간 O(1)O(1): 입력 크기에 상관없이 항상 일정한 시간이 걸리는 경우. 예: 배열에서 특정 인덱스에 접근하는 경우.
- 로그 시간 O(logn)O(\log n): 입력 크기가 커질수록 실행 시간이 느리게 증가하는 경우. 예: 이진 탐색.
- 선형 시간 O(n)O(n): 입력 크기에 비례하여 시간이 증가하는 경우. 예: 배열에서 모든 요소를 한 번씩 탐색하는 경우.
- 선형 로그 시간 O(nlogn)O(n \log n): 입력 크기에 선형적으로 증가하면서도 로그 시간만큼 추가적으로 시간이 걸리는 경우. 예: 효율적인 정렬 알고리즘인 퀵 정렬, 병합 정렬.
- 이차 시간 O(n2)O(n^2): 입력 크기에 제곱으로 시간이 증가하는 경우. 예: 이중 루프를 사용한 버블 정렬이나 삽입 정렬.
- 지수 시간 O(2n)O(2^n): 입력 크기가 증가할 때 실행 시간이 매우 빠르게 증가하는 경우. 예: 피보나치 수를 재귀적으로 계산하는 단순 알고리즘.
- 팩토리얼 시간 O(n!)O(n!): 입력 크기가 증가할 때 가장 빠르게 실행 시간이 증가하는 경우. 예: 순열을 모두 생성하는 알고리즘.