알고리즘

알고리즘

-컴퓨터로 문제를 풀기 위해 만든 단계적인 절차

-문제해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서

알고리즘의 조건

-입력(input): 0개 이상의 입력이 존재해야함

-출력(output): 1개 이상의 출력이 존재해야함

-명확성: 각 명령어의 의미는 명확해야함

-유한성: 한정된 수의 단계 후에는 반드시 종료되어야 함

-유효성: 각 명령어들은 실행 가능한 연산이어야 함

알고리즘 표현방식

1. 자연어

-사람이 읽기 쉬움

-의미 전달이 모호해질 수 있음 (명확성↓)

2. 흐름도

-직관적이고 이해가 쉬움

-알고리즘이 복잡해질수록 흐름도도 같이 복잡해짐

3. 유사코드 (= 의사코드) 

유사 코드 예시

-알고리즘의 핵심에 집중

-다양한 프로그래밍 언어로 변환이 용이

4. 프로그래밍 언어

-알고리즘에 대한 정확한 기술 가능

-알고리즘 핵심에 대한 이해를 방해함

 

ADT (추상 자료형)

-데이터나 연산이 무엇인지 정의하나 어떻게 구현할 것인지는 정의하지 않음

-객체와 연산(인터페이스)으로 구성됨

 

알고리즘 성능 분석

-공간 복잡도: 알고리즘을 프로그램으로 실행, 완료까지 필요한 총 저장공간의 양 (공간 복잡도=고정공간+가변공간)

 

-시간 복잡도: 알고리즘을 프로그램으로 실행, 완료까지 총 소요시간

• 수행시간 측정: 실제 수행시간을 측정, 구현이 필요하며 동일한 하드웨어를 사용해야함
• 알고리즘 복잡도 분석: 구현 없이 알고리즘이 수행하는 연산 횟수를 측정, 비교 (빅오 표기법 사용)