한국외대 신찬수 교수님 자료구조와알고리즘

자료구조(Data Structure), 알고리즘(Algoritm)

자료: data -> [저장공간(memory) + 읽기,쓰기,삽입,삭제,탐색(연산)] => 구조
알고리즘: data (유한한 횟수의 연산들) 입력-> 정답 출력

자료구조 (예:) 1. 변수(variable) 2.배열(array), 리스트(list)
알고리즘 (예:) 100개의 정수: 리스트 A:입력 -> 오름차순 정렬:출력

1
2
3
4
5
6
7
8
9
10
11
12

a = 5 # 쓰기 연산
print(a) # 읽기 연산

A = [3, -1, 5, 7]
'''
접근: 원소의 index
읽기, 쓰기: A[3]
삽입: A.append(9) # 맨 끝에 추가,
      A.insert(0, 100) # 0번째 idx에 100 값 추가
삭제: A.pop() # 가장 마지막 제거,
      A.pop(2) # 2번쨰 idx 값 제거
'''

인류 최초의 알고리즘

ac, 페르시아, Algebra 수학자 Al-khwarizmi
-> Algorismus + Arithmos => [Algorithm]

최대공약수(GCD)계산 알고리즘 by Euclid

1
2
3
4
5

def gcd(a, b):
    while a!=0 and b!=0:
        if a>b: a = a-b
        else: b = b-a
    return a+b

date: 2022-09-20 23:26:03
Big O notation
Big Ω notation/ Big θ notation
Big O notation

시간 복잡도(점근적 실행 시간, asymptotic runtime)

• O(big-O): 시간의 상한
  배열의 모든 값을 출력하는 알고리즘은 O(N)으로 표현할 수 있지만
  O(N^3),O(N^2),O(2^N)도 옳은 표현이다.
  다시 말하자면 알고리즘의 수행 시간은 적어도 이들 중 하나보다 빠르기만 하면 된다.

• Ω (big-Omega): 시간의 하한
  배열의 모든 값을 출력하는 알고리즘은 Ω(N) 뿐만 아니라 Ω(logN) 혹은 Ω(1)로도 표현할 수 있다.결국, 해당 알고리즘은 Ω 수행 시간보다 빠를 수 없게 된다.

• θ (big-theta): 딱 맞는 수행 시간
  θ는 O와 Ω 둘 다 의미한다. 즉, 어떤 알고리즘의 수행시간이 O(N)이면서 Ω(N)이라면, 이 알고리즘의 수행 시간을 θ(N)로 표현할 수 있다.

공간 복잡도

• 사용하는 스택 공간 또는 공간 복잡도 계산에 포함된다.
• 함수들이 호출 스택에 동시에 존재하지 않으면 계산에 포함되지 않는다.

1. 상수항은 무시하라
   O(N) = O(2N)
2. 지배적이지 않은 항은 무시하라
   O(N^2) = O(N^2 + N)
3. 여러 부분으로 이루어진 알고리즘: 덧셈 vs 곱셈

• O(A+B)
  만약 알고리즘이 “A 일을 모두 끝마친 후에 B일을 수행하라”의 형태라면 A와 B의 수행 시간을 더해야 한다.
• O(A*B)
  만약 알고리즘이 “A 일을 할 떄마다 B 일을 수행하라”의 형태라면 A와 B의 수행시간을 곱해야 한다.