[파이썬 알고리즘 인터뷰] Chap4. Big-O, Data Structure

본 포스팅은 책만 출판사에서 출간한 박상길 님의 '파이썬 알고리즘 인터뷰'를 바탕으로 작성된 포스팅입니다. 개인 공부 목적으로 책을 통해 공부한 알고리즘의 주요 내용들을 요약. 정리합니다.

 

이미지 출처: 교보문고

요약정리

Big-O

• Big-O는 알고리즘을 다루는 모든 책에 등장하는 중요한 개념이다
• 알고리즘이 얼마나 효율적인지 효율성을 나타내는 지표라고 생각해볼 수 있다
• 빅오는 입력값이 무한대로 커질 때 점근적 실행 시간(Asymptotic Running Time)을 표기하는 수학적 표기법 중 하나이다
• 상한
  • 주어진 경우에서 알고리즘이 수행하는 시간의 상한을 의미한다.(가장 느리게 수행하는 시간!)
• Amortized Analysis(분할 상한)
  • 해당 경우 알고리즘이 수행하는 최악의 경우만 고려하는 것은 극단적이지 않을까?
  • 최악의 경우를 여러 번에 걸쳐 나누는 형태로 알고리즘 시간 복잡도를 계산할 수 있다

• 병렬화(Parallism)
  • 최근 딥러닝의 발달과 함께 주목받고 있는 개념이다
  • 병렬화로 알고리즘의 실행시간을 단축시킬 수 있다
  • 따라서 최근 알고리즘의 시간 복잡도와 함께 고려되는 중요 요인이 되었다

 

Data Structure

• Python의 자료형과 특징을 알 수 있어야 한다
• 가변 자료형과 불변 자료형의 특징
  • List는 파이썬에서 유일한 가변 자료형이다
  • 우리가 자주 쓰는 숫자, 문자열은 불변 자료형이다
• 파이썬은 모든 것이 객체이다.
  • 이는 파이썬이 그만큼 편리한 기능 제공을 우선시한다는 것을 의미한다
  • 원시 타입 자료형에 비해 파이썬 객체는 계산이 느리다는 단점이 있다
  • 대신 파이썬은 훨씬 다양한 기능과 편의성을 제공해준다

 

출처

출처: <파이썬 알고리즘 인터뷰>(박상길 지음, 책만, 2020)