자료구조[큐,링키드리스트,트리 등 정리자료]

1. Algorithm and Complexity

자료구조에서 알고리즘과 복잡도는 핵심적인 개념이다. 알고리즘은 문제를 해결하기 위한 일련의 단계나 절차를 의미하며, 복잡도는 이 알고리즘이 효율적으로 작동하는지를 평가하는 척도이다. 알고리즘의 성능은 주로 시간 복잡도와 공간 복잡도로 구분된다. 시간 복잡도는 알고리즘이 문제를 해결하는 데 필요한 시간을 정량적으로 분석하는 것을 의미한다. 일반적으로 입력의 크기 n에 대해 알고리즘의 실행 시간이 어떻게 변화하는지를 측정한다. 이는 보통 Big O 표기법을 사용하여 표현되며, 예를 들어 O(, O(n), O(log n), O(n^ 등으로 구분된다. 이 표기법은 알고리즘의 성능을 대략적으로 파악할 수 있게 해준다. 상수 시간 O(은 입력 크기와 관계없이 일정한 시간이 소요됨을 의미하고, 선형 시간 O(n)은 입력 크기에 비례하여 실행 시간이 증가한다는 것을 나타낸다. 이러한 시간 복잡도를 통해 특정 알고리즘이 주어진 문제에 적합한지를 평가할 수 있다. 공간 복잡도는 알고리즘이 실행되는 동안 필요한 메모리의 양을 측정하는 것이다. 이는 알고리즘이 사용하는 변수, 데이터 구조, 입력 데이터 등을 포함하여 전체 메모리 사…