알고리즘 소개2

- 최댓값 찾기

1. 모두 일일이 비교 (n-1번)

2. 토너먼트 방식 (n-1번)

-> 효율성은 같다. 어떤 알고리즘을 써도 상관 없다.

- 뒤섞인 카드에서 원하는 카드 찾기

1. 순차탐색 (sequential search) -> n-1 번

- 순서대로 나열된 카드에서 찾기

1. 이진탐색 (binary search) ->

- 알고리즘 설계 기법

- 주어진 문제, 속성, 조건 등의 매우 다양

-> 일반적이고 범용의 기법 x

- 대표적인 방법

- 분할정복

- 동적 프로그래밍

- 욕심쟁이

- 알고리즘 분석

- 정확성 분석 ==> 여기선 다루지 않을 것

- 유효한 입력, 유한 시간 -> 정확한 결과 생성?

- 다양한 수학적 기법을 사용해서 이론적 증명이 필요

- 효율성

- 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정

- 메모리 양 -> 공간 복잡도

- 정적 공간 + 동적 공간

- 수행시간 -> *시간 복잡도

- 시간 복잡도

- 알고리즘을 프로그램으로 구현해서 이를 컴퓨터에서 실행시켜 실제 수행 시간을 측정

-> 일반적 x (컴퓨속도, 프로그래밍 언어, 프로그램 작성 방법, 컴파일러의 효율성 등 종속적)

- 알고리즘이 수행하는 기본적인 연산의 횟수의 합

- 입력 크기 n이 증가하면 수행 시간도 증가

-> 단순히 단위 연산의 개수가 아닌 입력 크기의 함수로 표현

- 입력 데이터의 상태에 종속적

- 평균 수행 시간

- 최선 수행 시간 ( 데이터가 이상적으로 주어졌을 때)

- 최악 수행 시간 ( 데이터가 최악으로 주어졌을 때) -> 이것을 사용

- 최악의 경우를 가정, 최악 수행 시간으로 시간 복잡도를 계산함

- 점근 성능, Big-Oh 표기 O(n)

- 점근 성능

- 입력 크기 n이 무한대로 커짐에 따라 결정되는 성능

- 수행 시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현

- 수행 시간의 어림값, 수행 시간의 증가 추세 파악이 용이 -> 알고리즘의 우열을 표현

- 점근 성능의 표기법

- 'Big-oh' 점근적 상한 (최악 수행 시간)

- 어떤 양의 상수 c와 n0이 존재하여 모든 n>= n0에 대하여

f(n)<=c*g(n)이면 f(n)=O(g(n))이다.

- 'Big-omega' 점근적 하한

- 'Big-theta' 점근적 상하한

- 주요 O-표기 간의 연산 시간의 크기 관계

O(1) < O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n)

효율적                                                                  비효율적

- 효울적인 알고리즘의 중요성

- 데이터 개수에 따라 비효율적인 알고리즘은 시간이 기하급수적으로 증가함.

- 알고리즘의 시간 복잡도 구하기

- 알고리즘의 수행시간 f(n)을 구한 후, 

- f(n) = O(g(n))을 만족하는 최소 차수의 함수를 찾음

- 반복문에 들어간 횟수를 구함 

- 반복문이 데이터 개수와 어떤 비례 관계를 가지는 지 확인

- 순환 알고리즘의 성능

- 순환 recursion, 재귀

- 알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 수행하는 행태

- 점화식으로 표현, ex) T(n) = T(n/2) + O(1), T(1) = c_1

-> T(n) = O(logn)

- 기본 점화식과 폐쇄형 6가지 -> 점화식과 같이 기억

T(n) = T(n-1) + Θ(1), T(1)=Θ(1) → Θ(n)
T(n) = T(n-1) + Θ(n), T(1)=Θ(1) → Θ(n^2)
T(n) = T(n/2) + Θ(1), T(1)=Θ(1) → Θ(logn)
T(n) = T(n/2) + Θ(n), T(1)=Θ(1) → Θ(n)
T(n) = 2T(n/2) + Θ(1), T(1)=Θ(1) → Θ(n)
T(n) = 2T(n/2) + Θ(n), T(1)=Θ(1) → Θ(nlogn)

- 퀵 정렬의 최악의 수행 시간 (n^2)

- 이진 탐색의 수행 시간 (logn)

- 합병 정렬의 수행 시간, 퀵 정렬의 최선의 수행 시간 (nlogn)