모각코_1주차

알고리즘이란?

그 지시대로 실행하여 특정한 일을 달성하려는 명령어들의 유한집합이다. 그리고 다음의 조건을 만족해야 한다.

• input , 0개 이상
• output, 1개 이상
• Definiteness 명확성, 모호 X
• Finiteness 유한성, 무한 loop X
• Effectiveness 유효성, 너무 복잡한 일 X

알고리즘 성능의 주요 판단

• Time
• Space(=메모리)

성능 측정 vs 성능 분석

성능 측정 (Measurement)	성능 분석 (Analysis)
특정 컴퓨터에서 시간과 공간을 실제로 측정	사용할 컴퓨터와 무관하게 필요한 시간과 공간을 이론적으로 추정

성능을 추정 분석한 결과 ⇒ 복잡도로 나타낸다.

✅ Space Complexity

프로그램이 실행을 마칠 때까지 필요한 메모리 양

✅ Time Complexity

프로그램 실행에 필요한 시간

🟡 Space Complexity

-크기가 고정

컴파일 시점에 미리 결정되어 고정된다.

-크기가 가변 !중요!

프로그램이 실행되는 동안에 동적으로 결정된다ㅏ.

필요한 배열의 크기, 연결 체인의 크기

재귀함수가 실행될 때 추가로 필요한 공간

---

🟡 Time Complexity

-프로그램의 실행시간이 중요

컴파일 시간은 중요 관심 대상 X

-분석방법?

연산의 개수 센다.

-연산 단위

사칙 연산, 비교연산 등 기본 연산

메모리에 할당(저장), 메모리로 부터 읽어 오기

배열의 인덱싱

입출력