패스트캠퍼스 챌린지 8일차

<학습일기>

Ch 08. 알고리즘 복잡도 표현 기법 - 시간복잡도

 

알고리즘 복잡도 표현 방법

- 일부 자료구조들은 시간복잡도를 검토해봐야한다.

1. 알고리즘 복잡도 계산이 필요한 이유

 - 하나의 문제를 푸는 알고리즘은 다양할 수 있다.

  - 정수의 절대값 구하기

   - 방법1: 정수값을 제곱한 값에 다시 루트를 씌우기

   - 방법2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기

   --> 다양한 알고리즘 중 어느 알고리즘이 더 좋은지 분석하기 위해, 복잡도를 정의하고 계산함.

2. 알고리즘 복잡도 계산 항목

 - 시간 복잡도: 알고리즘 실행 속도

 - 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

 --> 가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 한다.

* 알고리즘 시간 복잡도의 주요 요소: 반복분이 지배한다!

* 생각해보기

- 자동차로 서울에서 부산을 가기 위해, 다음과 같이 항목을 나누었을때, 가장 총 시간에 영향을 많이 미칠 것 같은 요소는?

 1. 자동차 문열기

 2. 자동차 문닫기

 3. 자동차 운전석 등받이 조정하기

 4. 자동차 시동걸기

 5. 자동차로 서울에서 부산가기

 6. 자동차로 시동끄기

 7. 자동차 문열기

 8. 자동차 문닫기

 --> 서울에서 부산가는 것이 가장 영향을 많이 미친다.

*마찬가지로, 프로그래밍에서 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문이다.

 --> 입력의 크기가 커지면 커질수록, 반복문이 알고리즘 수행 시간을 지배한다.

* 알고리즘 성능 표기법

1. Big-O(빅-오) 표기법 O(N)

 - 알고리즘 최악의 실행 시간을 표기

 - 가장 많이/일반적으로 사용함

 - 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 떄문

2. Ω (오메가) 표기법:  Ω(N)

 - 오메가 표기법은 알고리즘 최상의 실행 시간을 표기

3. Θ (세타) 표기법: Θ(N)

 - 오메가 표기법은 알고리즘 평균 실행 시간을 표기

--> 시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중 최악의 시간인 Big-O 표기법을 중심으로 익히면됨.

 

<학습일기>

- 시간 복잡도에서 왜 Big-O를 사용하는지, 복잡도에서 왜 공간복잡도가 아닌 시간복잡도를 사용하는지 몰랐는데 이번 강의를 통해서 알게 되었다!

---

 

<수강인증>

강의 수강

 

필기

---

*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.*

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

 

#패스트캠퍼스 #패캠챌린지 #직장인인강 #직장인자기계발 #패스트캠퍼스후기

#알고리즘기술면접완전정복올인원패키지Online