[파이썬으로 배우는 알고리즘 기초] 1. 알고리즘의 개념

1-1. 알고리즘이란?

• 어떤 문제를 컴퓨터로 풀기 위한 효율적인 절차로, 단계별로 명확하게 기술됨
• 새로운 문제를 만났을 때, 알고리즘 설계 기법을 통해 다양한 방법으로 해결할 수 있는 능력을 기르기 위해 공부함

---

1-2. 알고리즘의 효율성

• 리스트 사용하지 않고 피보나치 수열 구현

n = int(input())

now_2 = 0
now_1 = 0
now = 0

for i in range(n):
    if i == 0:
        now_2 = i
    elif i == 1:
        now_1 = i
    else:
        temp = now
        now_2 = now_1
        now_1 = temp
    now = now_2 + now_1
    print(now, end = ' ')

---

1-3. 알고리즘의 분석과 차수

1) 분석

• 정확성: 모든 입력 사례에 대해 해답을 찾을 수 있는가?
• 효율성: 입력 크기가 커지면 성능이 어떻게 변화하는가? --- 시간 복잡도 / 공간 복잡도
• 측정 기준
  - 퍼포먼스: 실행 시간이나 실행 명령 수 --- 컴퓨터의 성능이나 프로그래밍 언어에 따라 달라질 수 있음
  - 복잡도: 입력 크기에 따른 단위 연산의 실행 횟수 --- 컴퓨터 성능이나 프로그래밍 언어와 무관
  
• 시간 복잡도
  - 입력 크기(n)에 대한 단위 연산 횟수의 함수 f(n)
• 입력 사례에 따른 시간 복잡도 분석
  - 일정 시간 복잡도: 입력 사례에 따라 달라지지 않음
  - 최악 / 평균 / 최적 시간 복잡도: 입력 사례에 따라 달라짐

 

2) 차수(Order)

• 알고리즘의 궁극적인 성능 분류
• 시간 복잡도 함수의 최고차항 차수만을 취함
• 점근적 표기법
  - 빅오(O): 복잡도 함수의 점근적 상한을 표기
  - 오메가(Ω): 복잡도 함수의 점근적 하한을 표기
  - 세타(Θ): 복잡도 함수의 점근적 상한과 하한을 동시에 만족 == 차수

 

 

 

※ 강의 링크: https://inf.run/v8Rn