[C로 배우는 자료구조] 시간복잡도와 점근적 분석(1)

하이루 ,, 개강을 해버렸음니다...

제가 이번에 학교에서 수강하는 자료구조 과목이

책이나 인프런 강의의 목차와 다르게 진행되기에

학교 수업에 맞춰서 강의를 듣도록 하겠습니다!!

 

그래서 시간복잡도부터!

 

 

 

시간복잡도 : 쉽게 말해 시간이 얼마나 걸리냐!

시간 복잡도는 실행 환경에 다라 달라지며

실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트 함

이때 횟수를 입력 데이터의 크기레 관한 함수로 표현한다

 

데이터의 크기가 같더라도 실제 데이터에 따라서 달라지는데

이때는 대푯값을 사용 

-> 대푯값 : 최악의 경우 시간 복잡도 , 평균 시간복잡도

     ->최악의 경우 : 최-경보다 시간이 많이 걸리진 않을을 의미,

                          평균보다 단순해서 더 많이 사용된다

---

점근적 표기법

데이터의 갯수가 n->∞ 일 때 수행시간이 증가하는 

growth rate로 시간복잡도를 표현하는 기법

등을 사용한다.

특징  : 간단, 비의존적, 광범위하게 사용됨

알고리즘의 포함된 연산들의 실행 횟수를 표기하는 하나의 기법

최고차항의 차수만으로 표시

->가장 자주 실행되는 연산 혹은 문장의 실행횟수를 고려하면 됨!

---

n에 관계없이 상수시간이 소요됨

->알고리즘의 시간복잡도 :  O(1)

실행횟수 n번

선형 시간복잡도를 가진다고 말함

->O(n)

 

실행횟수 n번

최악의 경우

->O(n)

: if문이 맞을 때 return i , 아니라면 -1

최악의 경우 저장된 모든 원소 쌍을 비교함

비교 연산의 횟수 n(n-1)/2

최악의 경우 시간복잡도 -> O(n^2)