[10분 테코톡] 🙋‍♂️제이의 시간복잡도

시간 복잡도는 알고리즘과 연관이 되어있다.

 

알고리즘이란? 

 

- 문제를 해결하기 위한 방법 ex)  - 온라인 코딩 테스트로 알고리즘 풀기 - 아침에 일어나서 회사까지 가는 법 - 점심메뉴 고르기

시간 복잡도란?

- 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계

 

 

 

 

< 구분운이 좋을 때(최선) 운이 나쁠 때(최악) >

순차 탐색 알고리즘	1번 비교	1,024번 비교
이진 탐색 알고리즘	1번 비교	10번 비교

이와 같은 실행 횟수의 비교를 일반화시켜보면, 데이터가 n개일 때 최악의 경우 시간 복잡도는 다음과 같이 빅 오(O) 표기로 표시할 수 있습니다.

< 구분 최악의 경우 시간 복잡도 빅 오 표기 >

순차 탐색 알고리즘	n	O(n)
이진 탐색 알고리즘	logn	O(logn)

빅-오 표기법은 최고차 항의 차수만 표기하는 방법으로 시간 복잡도를 표현할 때 자주 사용됩니다. 즉, n2 + n + 1을 빅 오 표기법으로 표현하면 O(n2)이 됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

[네이버 지식백과] 시간 복잡도 [Time Complexity] (소프트웨어 어휘 다지기 - 중등)

 

< 영상 >

https://www.youtube.com/watch?v=IEH3YA2Nn4Q