시간 복잡도(Time Complexity)

시간 복잡도는 알고리즘이 실행되는 동안 소요되는 시간의 총량을 나타내는데, 이는 입력 크기에 따라 어떻게 증가하는지를 나타내는 척도입니다. 알고리즘의 효율성을 평가하는 중요한 지표 중 하나입니다.

빅 오 표기법(Big O Notation)

빅 오 표기법은 알고리즘의 시간 복잡도를 나타내는 수학적 표기법 중 하나입니다. 주어진 함수의 상한을 나타내며, 알고리즘의 성능을 최악의 경우로 표현합니다.

Array의 시간 복잡도

  • 접근(O(1)): 배열은 인덱스를 통해 직접적으로 요소에 접근할 수 있습니다. 따라서 인덱스를 이용한 요소의 읽기와 쓰기는 상수 시간이 소요됩니다.

  • 삽입 및 삭제(O(n)): 배열에서 요소를 삽입하거나 삭제할 때, 해당 요소 뒤의 요소들을 이동해야 합니다. 따라서 이러한 작업은 배열의 길이에 비례하여 선형 시간이 소요됩니다.

Linked List의 시간 복잡도

  • 접근(O(n)): 링크드 리스트는 특정 위치에 직접 접근할 수 없으므로, 특정 요소에 접근하기 위해서는 처음부터 해당 요소까지 순회해야 합니다.

  • 삽입 및 삭제(O(1)): 링크드 리스트에서는 삽입 또는 삭제할 요소의 바로 앞 노드에 대한 포인터만 변경하면 되므로, 상수 시간만 소요됩니다.

장, 단점

Array는 빠른 접근이 가능하지만 삽입 및 삭제에 비용이 크며, Linked Lis는 삽입 및 삭제가 빠르지만 접근에는 비용이 큽니다.