반응형 동굴 속 정보183 빅오(Big O) 시간복잡도 [ Big O, 시간복잡도 ] 빅오(Big O) 시간복잡도는 위 그림하나도 전부 설명이 가능하다. 빅오는 처리시간이 아니라 시간의 증가율을 나타낸다고 보면 된다. X는 데이터의 갯수, Y는 처리의 갯수이다. 순서를 보면 $O(2^n)$ > $O(n^2)$ > $O(n log n)$ > $O(N)$ > $O(log n)$ > $O(1)$ 이다. 참고로 빅오 표기법에서 상수는 연산에 고정된 값이라서 연산에 크게 작용하지 않는다고 본다. 그래서 상수 10을 빅오랑 곱해도 값은 빅오 그대로 라는 것을 알아야 한다. 예를들어 $10 \times O(1)$ = $O(1)$ 이다. 시간 증가량에 대한 표기법은 점근적 상한(Upper Bound)인 Big-O 외에 점근적 일치(Tight Bound)인 Big-Theta.. 2021. 4. 10. Dynamic Programing Algoritm [ 다이나믹 프로그래밍 ] 다이나믹 프로그래밍(Dynamic Programing)은 메모리를 적절하게 사용하는 방법으로 알고리즘의 수행 시간을 향상시키는 것을 목적으로 둔다. 메모리는 작은 문제라고 불리는 이미 계산된 결과를 저장하는 데 사용된다. 다이나믹 프로그래밍을 구현하는 방법은 탑다운 방식과 바텀업 방식 이렇게 두 가지로 알려져 있다. 결과적으로는 이렇게 작은 문제를 저장해서 이미 계산된 내역을 메모리에서 빠르게 찾아서 문제를 해결한다는 것이다. 이런 문제를 해결할 수 있는 조건이 두가지가 있는데 하나는 최적 구조이고 다른 하나는 중복 구조이다. 최적 구조는 큰 문제를 작은 문제로 쪼개서 처리할 수 있는 구조를 말하고 중복 구조는 같은 문제가 반복적으로 나오는 구조로 볼 수 있다. 대표적인 중복문.. 2021. 4. 10. 최적 알고리즘과, 루프 불변성 [ 알고리즘 분석 기준] 최적 알고리즘을 찾기 위해서 가장 먼저 해야할 일은 문제를 풀 수 있는 가장 효율적인 알고리즘을 고안하는 것이다. 그 후 이 알고리즘의 작업량(W(n))을 구한다. 이 문제를 풀 수 있는 다른 알고리즘의 작업량(F(n)과 개발자가 고안한 알고리즘의 작업량이 같거나 적은지 확인한다. 작업량 W(n)과 F(n)이 같거나 적다면 최적의 알고리즘으로 본다. 알고리즘에 대해서 분석하기 위한 기준으로 "최단정수기"가 있다. 최단정수기는 (1) 최적성, (2) 단순성, (3) 정확성, (4) 수행성, (5) 기억장소 사용량을 말한다. 이 다섯가지 기준을 활용해서 알고리즘을 말할 수 있고 평가할 수 있다. (1) 최적성 제작한 알고리즘보다 더 적은 연산을 수행하는 알고리즘이 없다는 것을 말한다.. 2021. 4. 10. 이전 1 ··· 18 19 20 21 22 23 24 ··· 61 다음 반응형
