빅오표기법 및 Linked list(링크드리스트)의 시간복잡도에 대하여....

시간복잡도를 설명하기전에....

모든 개발자는 자신만의 시간 관념이 있습니다. 개발자들은 대부분의 시간을 사용자들에게 쏟아붓기 때문에, 최대한 시간을 효율적으로 사용하고 싶어하죠. 시간복잡도 를 최소화 함으로써 이게 실현가능해집니다

.프로그래밍에서 시간복잡도를 이해하기 전에, 먼저 이 시간복잡도가 알고리즘에서 흔하게 활용된다는 사실을 기억해야합니다

알고리즘은 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 의미합니다.

하나의 예시를 들면?..

밥짓는것을 예로 들어봅시다.

1. 쌀통에 쌀을 담는다.

2. 쌀을 물로 씻는다.

3. 적당량의 물을 담는다.

4. 밥솥에 넣고 취사버튼을 누른다.

5. 완료!!.

밥도 물을 어떻게 넣는냐에 따라 다르고..고산시대에서 밥을 짓거나.. 냄비로 지을떄도 다르겠죠.

이런 상황말고도 어떤 변수와 상황에 따라 어떻게 될지 모릅니다.

결국 시간복잡도를 분석 하는 것은 input n 에 대하여 알고리즘이 문제를 해결하는 데에 얼마나 오랜 시간이 걸리는 지를 분석하는 것 과 같습니다.

그리고 이를 Big-O 표기 를 이용하여 정의할 수 있습니다.

일단 대표적인 시간복잡도를 설명해보도록 하겠습니다.

O(1) – 상수 시간 : 입력값 n 이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거칩니다. 1~999999일정한 상수...
O(log n) – 로그 시간 : 입력값 n 이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듭니다.
O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가집니다. 2n -> n 으로표시
O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱입니다.
O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱입니다.