코젤브

- Big O 표기법 = worst와 비슷 : 점근적 상한 : 궁극적으로 이것보단 좋다(=기울기가 같거나 낮다) - Ω 표기법 : 점근적 하한 : 아무리 좋아도 이것보다 좋아질 수 없다(=기울기가 높다) - Θ 표기법 : 점근적 협소 : 차수가 같다(=기울기가 같다) - Small o 표기법 : 차수가 작다(=기울기가 낮다) (같을 수 없다) - 차수의 주요 성질 g(n) ∈ O(f(n)) f(n) ∈ Ω(g(n)) g(n) ∈ Θ(f(n)) f(n) ∈ Θ(g(n)) 로그 복잡도 함수는 모두 같은 카테고리 => Θ(lg n) 지수 복잡도 함수는 모두 같은 카테고리 X n! 는 어떤 지수 복잡도 함수보다 나쁨 좋은 것부터 나열 n c ≤ 0, d > 0 일 때, g(n) ∈ O(f (n)), 그리고 h(..

- 알고리즘의 분석 시간복잡도 분석: 입력 크기에 따라 단위연산이 몇번 수행되는지 결정하는 절차 표현 척도 - 단위연산: 비교, 지정 … - 입력 크기: 배열 크기, 리스트의 길이, 행렬에서 행과 열의 크기 … - 알고리즘 분석 방법의 종류 모든 경우 분석: (입력 크기에만 종속) 입력값과 무관하게 결과값 일정 => 적용 한정적 최악 경우 분석: (입력 크기와 입력 값에 종속) 단위연산의 수행횟수 최대 평균 경우 분석: (입력 크기와 입력 값에 종속) 평균 최선 경우 분석: (입력 크기와 입력 값에 종속) 단위연산의 수행횟수 최소 - [예시] 배열 덧셈 알고리즘 : 배열에 있는 모든 수를 더해라 case1) 단위연산: 덧셈 입력 크기: 배열의 크기 n 모든 경우 분석: 루프가 n번 반복, 따라서 T(n)..

- 순차검색 알고리즘 위치에 따라 검색 양이 다름. 최악의 경우: n -> 그렇지만 순차 검색이 비효율적인 알고리즘(본 내용을 또 보는 알고리즘)은 아니다. - 이분검색 알고리즘 (정렬된 배열에서 찾는) while문을 수행할 때 마다 검색 대상 크기가 반으로 감소하기 때문에 최악의 경우: lg n + 1 - 피보나치 수열 재귀적 방법 -> 중복 계산 문제 - 수행 속도가 매우 느림 (중복 계산 문제) - fib(n)의 호출 횟수 = 재귀 트리의 노드 개수 = T(n) > 2n/2 반복적 방법 -> 속도 훨 빠름 - 수행 속도가 훨씬 빠름 (중복 계산 X) - 계산하는 항의 총 개수 T(n) = n+1 두 알고리즘의 비교

- 강좌의 목표 : 설계, 분석, 계산적 복잡도(문제 자체의 복잡도) - 알고리즘 : 각 단계가 명확하게 정의되고 실행이 가능한 유한 시간대에 종료되는 어느정도의 일반성을 가진 일련의 절차 - 알고리즘의 요구조건 유한시간 내 종료 termination 명확성 definiteness 실행 가능성 executableness 기타: 일반성 generality - 프로그램 설계 과정 - 문제의 표기 방법 - 문제: 답을 찾고자 던지는 질문 - 파라미터(parameter): 문제에서 특정값이 주어지지 않은 변수 - 문제의 사례(입력): 파라미터에 특정 값을 지정한 것 - 사례에 대한 해답(출력): 주어진 사례에 관한 질문에 대한 값 - 알고리즘의 표기 : C++에 가까운 의사코드 사용 (자연어, 프로그래밍 언어 ..