TIL 웹개발 - 알고리즘이란?
파이썬 과정을 마치고 알고리즘과 자료구조에 대한 강의를 시작했다. 알고리즘이란? 같은 문제를 풀더라도 공간적으로 시간적으로 더 효율적으로 풀기 위한 것 시간 복잡도 입력값과 문제를 해결하는데 걸리는 시간과의 상관관계를 말한다. 입력갓이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 ㅐ로 늘어나는지 보는 것. 공간 복잡도 입력값과 문제를 해결하는데 걸리는 공간과의 상관관계를 말한다. 입력값이 2ㅐ로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것. 점근 표기법 알고리즘의 성능을 수학적으로 표기하는 기법으로 알고리즘의 '효율성'을 평가하는 방법이다. 빅오(Big-O) 표기범 최악의 성능이 나올때 어느정도 연산량이 걸릴지 표기 방법: O(N) N은 얼마나 계산하냐를 말하기 때문에 for문이 한번 있으면 O(N)으로 사용하고 for문이 2개 중첩된 알고리즘은 O(N제곱) 으로 표기한다. 빅 오메가(Big -Ω) 표기법 최선의 성능이 나올때 어느정도의 연산량이 걸릴지 표기 방법: Ω(1) 빅 오메가는 거의 사용하지 않는다. 왜냐하면 보통 최악의 경우를 대비하기때문. 최선은 가장 좋으면 1이지만 최악은.... 상상하기 싫다. 알파벳 찾기 문제
- 서경태