오늘은! 문제를 풀지 않았다. 왜냐하면 정렬 문제를 다 풀었고 새로운 알고리즘 문제나 자료구조를 풀기에는... 오늘이 금요일이었기 때문... 원래 시작은 월요일이 좋은 거니까 ^^

그래서 오늘은 시간복잡도에 대해서 공부해보려고 한다! 시간복잡도에 대해서 전~혀 모르고 있을 뿐더러 시간복잡도 표기 방식이 3개나 있는 줄도 몰랐기 때문에!... 일단 오늘은 간단하게 공부하는 걸로! 차차 자세히 알아가면서 공부해야지.

1. 시간 복잡도 (Time Complexity)

일단 시간 복잡도라는 것은 '시간'에 관한 복잡도이다. 알고리즘의 복잡도는 2가지가 존재한다. 오늘 다룰 시간 복잡도와, 메모리와 관련된 공간 복잡도이다. 말 그대로 시간 복잡도는 이 알고리즘이 결과에 도달하는 데까지 걸리는 시간과 입력의 함수 관계를 가리킨다. 시간 복잡도에 영향을 주는 주요 요소는 반복문이다. 반복되는 횟수가 많아질수록, 여러 반복문이 중첩될수록 시간 복잡도는 커지게 된다.

1. 알고리즘 성능 표기법

알고리즘의 성능을 표기하는 방법은 아래의 세 가지이다. 이 중에서 내가 가장 많이 보고, 실제로도 가장 많이 쓰는 표기법은 Big-O(빅 오) 표기법이다.

1. Big-O(빅 오) 표기법: O(n)
   알고리즘의 최악의 실행 시간 표기
2. Big-Ω(빅 오메가) 표기법: Ω(n)
   알고리즘의 최상의 실행 시간 표기
3. Big-θ(빅 세타) 표기법: θ(n)
   알고리즘의 평균 실행 시간 표기

2. Big-O(빅 오) 표기법

내가 이해하는 Big-O 표기법은 y=f(n) 과 같다.
시간 복잡도의 크기 순서는

이와 같다. 이를 그래프로 나타내면

이렇게 나타낼 수 있다.
(출처: https://velog.io/@keemtj/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84)

여기서 각각의 표기법에 대한 추가 설명을 덧붙여보자.

• O(1): 입력이 n이든, 1, 10, 100든 어떤 수가 와도 상관없이 무조건 상수값만큼 실행
• O(n): 입력 n에 따라서 n, n+1, 3n+1번 등을 실행

이와 관련해서는 조금 더 공부해야할 것 같다...