[Lecture] Week 1 & 2 알고리즘: 효율, 분석, 차수
알고리즘의 정의
: 문제를 해결할 수 있는 잘 정의된(well defined) 유한(finite)시간 내에 종료되는 계산적인(computational) 절차(precedure)
Algorithm과 Method의 차이점
알고리즘은 유한 시간내에 종료되나, method는 유한 시간내에 종료 되는지 모른다!
알고리즘 분석 방법
문제의 표기 방법
- 문제 : 답을 찾고자 던지는 질문
- 파라미터(parameter) : 문제에서 특정값이 주어지지 않은 변수
- 입력 : parameter에 특정 값을 지정한 것
- 출력 : 주어진 입력에 대한 문제의 답
Ex 1.1) Sorting
- 문제 : n개의 수로 구성된 리스트 S 를 비내림차순(nondecreasing order)으로 정렬(sort)하라
- 파라미터: S, n
- 사례(instance) – 파라미터에 어떤 값을 대입한 경우
Ex 1.2) Searching
- 문제: 어떤 수 x가 n개의 수로 구성된 리스트 S 에 있는지 결정하라. S 에 있으면 “예”, 없으면 “아니오”로 답하시오
- 파라미터: S, n, x
Pseudo-code(의사코드)
Ex 1.1) Sorting
- 문제 : n개의 수로 구성된 리스트 S 를 비내림차순(nondecreasing order)으로 정렬(sort)하라
- 파라미터: S, n
- 사례(instance) – 파라미터에 어떤 값을 대입한 경우
Ex 1.2) Searching
- 문제: 어떤 수 x가 n개의 수로 구성된 리스트 S 에 있는지 결정하라. S 에 있으면 “예”, 없으면 “아니오”로 답하시오
- 파라미터: S, n, x
: 직접 실행할 수 있는 프로그래밍언어는 아니지만, 거의 실제 프로그램에 가깝게 계산과정을 표현할 수 있는 언어이다. 간결하면서 정확하게 의미를 표현가능하다. 알고리즘은 의사코드를 사용하여 표현한다.
배열 (Array)
: 공통의 성질을 갖는 변수가 여러 개 일 때 하나의 변수명을 정하고, 위치를
나타내는 인덱스를 이용해서 변수를 나타내는 자료구조 (data structure)
[배열에 저장된 10개의 수 중 최대값 찾기]
- Pseudo-code
1) a[0]의 데이터를 임시로 최대값 M으로 설정
2) a[1]의 값과 M과 비교해서, a[1]이 더 크면 a[1]을 M으로 재설정, 아니면 a[2]값 비교로 이동
3) step 2를 나머지 데이터에 대해서 수행
4) M이 데이터의 최대값
Flow-chart(흐름도)
Examples
Alg 1.1 순차검색 알고리즘
Pseudo-code
구현
Pseudo-code
구현
1) Python
# Seqeuntial Search
def seqsearch(s, x):
loc = -1
for i in range(len(s)):
if s[i] == x:
loc = i
return loc
s = [3,5,2,1,7,9]
loc = seqsearch(s,4)
print(loc)
Alg 1.2 배열의 수 더하기
Pseudo-code
구현
1) Python
# Sum of elements of array
def sum1(s):
result = 0
for a in s:
result += a
return result
def sum2(s):
result = 0
for i in range(len(s)):
result += s[i]
return result
s = [3,5,2,1,7,9]
answer1 = sum1(s)
answer2 = sum2(s)
print(answer1, answer2)
Alg 1.3 교환정렬
Pseudo-code
구현
1) Python
# Select1ion Sort - nondecreasing order
def Selection_Sort(S):
for i in range(len(S)):
for j in range(i+1, len(S)):
if S[j] < S[i]:
temp = S[i]
S[i] = S[j]
S[j] = temp
return S
s=[3,2,5,7,1,9,4,6,8]
s = Selection_Sort(s)
print(s)
Alg 1.4 행렬의 곱셈
Pseudo-code
구현
# Matrix Multiplication
def Matrix_Multiplication(a, b):
result = [[0] * len(b) for row in range(len(a))]
for i in range(len(a)):
for j in range(len(b)):
for k in range(len(a[0])):
result[i][j] += a[i][k] * b[k][j]
return result
a = [[1,2], [3,4]]
b = [[4,1], [1,0]]
print(Matrix_Multiplication(a,b))
Alg 1.5 Binary Search
Pseudo-code
구현
# Binary Search
def binary_search(data, item, low, high):
location = -1
while (low <= high) and (location==-1):
mid = int((low + high) / 2)
if data[mid] == item:
location = mid
elif data[mid] > item:
high = mid-1
else:
low = mid+1
return location
data = [1,3,5,6,7,9,10,14,17,19]
n = len(data)
location = binary_search(data, 9, 0, n-1)
print(location)
Alg 1.6 Fibonacci
Pseudo-code
1) Recursion(재귀)
2) Iteration(반복)
구현
# Fibonacci
# Recursive way
def fib1(n):
if n <= 1:
return n
else:
return fib1(n-1) + fib1(n-2)
# Iterative way
def fib2(n):
fib = [0 for i in range(n+1)]
if n > 0:
fib[1] = 1
for i in range(2,n+1):
fib[i] = fib[i-1] + fib[i-2]
return fib[n]
알고리즘의 분석
분석 방법의 종류
Every-case analysis
: Input data의 size에만 종속된다. Input data의 value와는 무관하다.
- Worst-case analysis
- Average-case analysis
- Best-case analysis
Author And Source
이 문제에 관하여([Lecture] Week 1 & 2 알고리즘: 효율, 분석, 차수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wilko97/Lecture-Week-1-2-알고리즘-효율-분석-차수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)