[자바로 구현하고 배우는 자료구조] 1.자바 특성 및 알고리즘 기본(1)

블로그에 하루에 하나씩 공부한 글을 올리려고 했는데 실패했다. 모두를 위한 컴퓨터 과학을 다 듣고 생각해보기에 답변하는 걸 하나의 글에 다 작성하다보니 수정만 하고있다. 게다가 쓰다가 잠들어서 작성한 걸 날렸다... 속상하지만 어쩔 수 없지.. 그래서 자바로 구현하고 배우는 자료구조는 한 챕터당 하나씩 써보려고 한다. 그리고 생각해보기를 작성하기 보단 교수님이 작성하신 필기를 바탕으로 내가 이해한 걸 글로 써보려고 한다. 참고로 모두를 위한 컴퓨터 과학에 비하면 교수님이 굉장히 조용하시긴 한데 그래도 재밌다. 

 

https://www.boostcourse.org/cs204

자바로 구현하고 배우는 자료구조

 

---

(1) 복잡성

1. 자료구조의 시작

수업에서 배우게 될 자료구조는 다음과 같다. - 연결리스트, 스택, 큐, 체인 해시, 트리, 여러 정렬 방식

2. 복잡성 소개

- 시간 복잡도의 규칙

(1) 입력값은 항상 0보다 크거나 같다(input  >= 0).

(2) 함수는 많은 입력값을 위해 더 많은 작업을 한다(functions do more work for more input).

(3) 상수는 빼고 생각한다(drop all the constants).

(4) 낮은 차수는 무시한다(ignore lower order terms).

(5) 로그의 밑 부분은 무시한다(ignore the base of logs).

 

- 시간복잡도

1, C - constant time

log n - trees

n - once per item

n^2 - compare all v all

n! - traveling sales

3. 빅 오 표기법

O	same or faster
o	faster
θ	same rate
Ω	same or slower
ω	slower

4. 빅 오 표기법 예시

• 빅 오 표기법 예시 문제 중 n=1을 대입하면 어떻게 되나요? 적당히 큰 수를 대입해야 하는 이유는 무엇인가요?
  - 시간의 차이를 알 수 없기때문에 큰 수를 대입해야 한다. 예를 들어 위 시간복잡도에 1을 직접 대입해보면 모든 결과값이 1이 나온다. 차이를 알 수 없다. 2만 대입해봐도 1, log2, 2, 4, 2 로 그 값의 차이를 알기가 어렵다. 우리가 시간복잡도 식을 만든 이유는 n이 무한대일 때를 염두하고 만든 식이기 때문에 가급적이면 큰 수를 대입해야 한다.