Big O

5일차 게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.59 ~ p. 70 내용 정리 6. big-O big-O 시간은 알고리즘의 효율성을 나타내는 지표 혹은 언어이다. 비유하기 파일을 보낼 때 크기가 작다면 전송하는게 빠르지만 굉장히 크다면 물리적으로 직접 가는게 빠를것.(1테라를 미국에 메일로 보내느니 들고 비행기타고 가는게 낫다!) 시간 복잡도 점근적 실행 시간(asymptotic runtime), 또는 big-O 시간에 대한 개념에 대해 얘기해보자. 데이터 전송 ‘알고리즘’의 실행 시간에서 온라인 전송: O(s), s가 파일의 크기이다. 파일의 크기가 증가함에 따라 전송 시간 또한 선형적으로 증가 비행기 전송: O(1), 파일 크기랑 상관없다. 크든 작든 비행기 한대 가는 시간이니까! O(s)가 커지다 보면 어느 순간 O(1)보다 커지게 된다. O(1)이 얼마든, O(s)가 얼마나 천천히 커지든 언젠가는 무조건! ...