2022-07-26
자료구조는 무엇일까?
자료구조란 무엇일까? 간단하게 정의와 Big O 표기법에 대해 간락하게 알아보자!
자료구조
자료구조란 데이터를 효율적으로 접근하고 사용할 수 있도록 조직하는 방법을 말한다.
가장 기본적인 배열, 해시, 트리, 그래프 등 여러 유형의 자료구조가 있다.
각 자료구조는 특성, 장점 및 사용 사례가 있으며, 적합한 자료구조를 선택하면 효율성에 큰 영향을 미친다.
시간 복잡도와 공간 복잡도
- 시간 복잡도:
알고리즘이 입력 크기에 따라 실행에 걸리는
시간을 측정한 것이다.
효율성을 분석하고 동일한 문제를 해결하기 위해 서로 다른 알고리즘을 비교할 수 있다.
시간 복잡도는 일반적으로 알고리즘의 실행 시간 증가에 대한 상한을 big O 표기법으로 나타낸다. - 공간 복잡도:
알고리즘이 입력 크기에 따라 실행에 소모되는
메모리 양을 측정한 것이다.
메모리의 증가에 대한 상한을 big O 표기법으로 나타낸다.
Big O 표기법
실행 시간 증가율 또는 알고리즘의 메모리 사용량에 대한 상한을 설명하는 데 사용되는 수학적 표기법이다.
실행 시간 또는 메모리 사용량의 증가율에 대한 상한선을 제공하므로 가능한 최대 증가율의 추정치만 제공한다.
실제 알고리즘 실행 또는 메모리 사용량이 big O 설명보다 낮거나 약간 높게 측정될 수 있다.
상수항을 제거하거나 가장 높은 지수만 표현되는 등 러프하게 표현된다.
O(n)과O(100)중 어느 것이 성능이 우수할까?
100단계 까지는 둘 다 같은 단계를 밟으나 n은 지속적으로 단계가 높아짐으로서 100을 훌쩍 넘게 될 것이다.
표현 방식
빅 오 표기법은 O(수학적 표기)의 형태로 나타낼 수 있는데 선형 시간, 지수 시간, 로가리즘 등 다양하게 표현된다.
간단한 예로 O(n, n^2, log n, n log n, 1, etc..)와 같이 나타낼 수 있다.