[코드트리] 시간, 공간복잡도 / 기호 변환,

 

파이썬에 대한 기초적인 문법 복습을 끝낸 후 바로 자료구조와 병행하기로 하였다.

첫 시간으로는 시간, 공간복잡도에 대한 학습을 진행하였다.

 

 

 

 

점근 표기법

---

 

 점근표기법에는 O, Ω, Θ가 있다. 각각 빅-오, 빅-오메가, 빅-세타라고 부른다.

 

코드트리에서 기초 개념을 학습할 수 있었고 다양한 예시로 살펴볼 수 있었다.

연습문제로 연습해보자.

 

1. 기호 변환

https://www.codetree.ai/missions/6/problems/translate-notation?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제에서 O(g(x)) 의 뜻은 가장 높은 차수와 같거나 높은 식을 의미한다. 따라서 위문제에서 f(x) 인 x ^8보다 차수가 같거나 높아야하므로  O(x^4)는 성립하지 않는다.

다음은 Ω(g(x))의 뜻은  가장 높은 차수와 같거나 낮은 식을 의미하므로 성립한다. x^8 = Ω(x^4)

다음 Θ(g(x))의 뜻은 최고차항(가장 높은 차수)을 뜻하므로 성립하지않는다.

다음 식에서 O(g(x))는 성립한다. 차수가 2로 같기때문이다 따라서 보기 4번은 가능하다.

그 다음식에서 Ω(g(x))는 성립한다. 차수가 2로 같기 때문이다. 따라서 보기 5번도 가능하다.

다음은 Θ(g(x))로 성립한다. 차수가 2로 같기 때문이다. 따라서 보기 6번도 가능하다.

 

 

 

2. 시간복잡도와 반복문 1

https://www.codetree.ai/missions/6/problems/time-complexity-and-for-loop-1?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

1. 아래 식에서 i가 1부터 n까지이므로 n 번 순회한다. 따라서 O(n)

2.  아래식에서는 1부터 n-5까지 순회한다. O(n-5)지만 빅오표기법에서는 단순화하여 표기하므로 O(n)

3. 아래식에서 대략 n/2번 순회한다.O(n*(1/2)) = O(n) 이므로 O(n)

4. 아래식에서 2*n번 순회한다. 이 또한 O(n)이다.