순환알고리즘의 성능은 '점화식'으로 구한다 # 순환(recursion, 재귀)알고리즘의 수행과정에서 자기자신의 알고리즘을 다시 수행하는 형태 예) 이진탐색의 수행시간을 구할 때의 점화식은,T(n) = T(n/2) + O(1), T(1) = c1 즉, 점화식 T(n)은 n/2개의 데이터를 처리하는 시간 T(n/2)과 상수시간 O(1)을 더한다.
#1 점근성능 입력크기(실제 처리하는 데이터 개수) n이 무한대로 커짐에 따라 결정되는 성능!데이터 개수가 증가하면 알고리즘 성능결정에 가장 큰 요인은 무엇인지 따지는 것! f(n) = 10n + 9 f(n) = n^2 / 2 + 3n n=5 59 27.5 n=10 109 80 n=15 159 157.5 n=16 169 176 n=20 209 260 ... ... ... 수행시간의 다항식 함수에서,데이터 개수가 증가할 수록(입력크기가 증가할 수록) 최고차항이 성능결정요인에 가장 큰 요인이 됨 계수없이 최고차항만으로 시간복잡도를 표현! 수행시간의 어림값이나 수행시간의 증가추세 파악이 용이하다 => 알고리즘의 우열을 표현! #2 점근성능 표기법 [정의1] 'Big-oh' 점근적 상한 ( O => 최악의 수행..
알고리즘의 '효율성 분석'을 위해, 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정- 메모리의 양(정적공간+동적공간) 계산 => 공간복잡도(space complexity)- 수행시간 => 시간복잡도(time complexity) => 수행시간을 통해 시간복잡도를 구하고 효율적인 알고리즘인지 분석한다.! # 시간복잡도(time complexity) 알고리즘을 프로그램으로 구현 => 컴퓨터에서 실행시켜 실제 수행시간을 측정하지만, 일반적이지 않다!(컴퓨터의 속도나 사용한 프로그래밍언어, 프로그램 작성법, 컴파일러의 효율성 등에 종속적) 그렇다면 시간복잡도란 무엇? 알고리즘이 수행하는 기본적인 연산의 횟수를 합한 것 ★★★ 시간복잡도에 영향을 미치는 요인 2가지① 입력으로 제공되는 데이터 크기 => 입력크기②..
#1 최대값 찾기 25 15 35 60 45 80 55 75 알고리즘 1 : 값들을 하나씩 모두 비교해가면서 최대값 찾기 알고리즘 2 : 토너먼트 방식 어떤 것이 효율적? => 몇 번의 비교연산을 해야 하는가? #2 "뒤섞인" 카드에서 원하는 카드 찾기 데이터 찾기 => 탐색 A 4 5 7 10 J K 순차적으로 왼쪽부터 하나씩 비교하며 탐색한다 => 순차탐색(Sequential search) 10 5 A J 7 K . ∴ 6번 뒤집어서 K 발견 #3 "순서대로 나열"된 카드에서 10 찾기 A45710JK 7 . . . 임의로 정 중앙에 있는 카드를 하나 뒤집어 본다 => 이진탐색(Binary search)순서대로 나열 되었으니까 뽑은 7번 카드 기준으로 오른쪽 카드만 확인한다 7 J 남은 오른쪽 카드 ..
"컴퓨터로 문제를 해결하려면, 해당 문제를 컴퓨터가 처리할수 있는 형태로 표현해야 한다." #1 정의 자료구조 란,컴퓨터 기억공간에 자료를 표현하고 조직화시키는 방법 사용하는 데이터 양 / 사용빈도 / 필요한 기억장치 양 / 원하는 작업 처리시간 / 데이터 성격 등 고려하여적절한 자료구조 선택 => 효율 UP #2 자료구조와 알고리즘의 관계 문제에 대한 자료구조 선택이 알고리즘 설계 및 효율에 큰 영향 #3 기본적인 자료구조 선형구조 - 배열과 연결리스트, 큐와 스택비선형구조 - 트리와 그래프
#1 정의 알고리즘(Algorithems)은,주어진 문제에 대해 결과를 도출하기 위해, / 모호하지 않고 / 간단하며 / 컴퓨터가 수행 가능한 유한 개의 일련의 명령들을 '순서대로' 구성한 것 #2 조건 알고리즘의 조건,입출력(input & output) : '0개 이상의 외부입력 + 하나이상의 출력' 필요명확성(definiteness) : 각 명령은 모호하지 않고 '단순 명확'할 것유한성(finiteness) : 한정된 수의 단계 후에 '반드시 종료'할 것유효성(effectiveness) : 모든 명령은 '실행가능' 할 것추가로,실용적 관점에서, 알고리즘의 효율성도 충분히 고려되고 만족되어야 할 조건! #3 생성단계 알고리즘 생성단계,주어진 문제의 출력 및 처리조건 고려하여 문제분석이를 토대로 설계 수..
