자료구조 및 실습 - [1] 알고리즘 분석 (1)

알고리즘이란?

  주어진 문제를 유한한 시간 내에 해결하는 단계적 절차

 

데이터 구조란? 

  데이터를 조직하고 접근하는 체계적 방식

 

 

우리는 좋은 알고리즘과 데이터구조를 설계하는 것에 관심이 있다. 여기서 '좋다'는 기준은

• 알고리즘과 데이터 구조 작업에 소요되는 실행시간
• 기억장소 사용량 (메모리 사용량)

에 따른다. 

 

따라서 어떤 알고리즘과 데이터 구조를 좋다고 분류하려면, 이를 분석하기 위한 정밀한 수단을 필요로 한다!

 

여기서 우리는 실행시간을 따지게 된다. 대부분의 알고리즘은 입력 -> 출력으로 변환하고, 

일반적으로 알고리즘의 실행시간(Running Time)은 대체로 입력의 크기(Input Size) 와 함께 커진다.

 

평균실행시간(average case running time)은 결정하기 어렵기에, 최악실행시간(Worst case running time)에 집중한다.

하지만 사용하는 하드웨어와 소프트웨어에 따라 알고리즘의 속도가 차이가 나게되므로 이에 무관하게 평가할 수 있어야 하는데, 이때 이론적 방법으로 실행시간을 구하게 된다. 이론적 방법으로 실행시간을 구할 때는 의사코드로 표현된 알고리즘, 의사코드 (Pseudo - code, 알고리즘을 설명하기 위한 고급 언어)를 사용한다.

배열의 최댓값 원소찾기에 대한 의사코드

의사코드를 보면 우리가 쓰는 자연어 문장보다 더 구조적이지만, 프로그래밍 언어보다는 덜 상세한 것을 알 수 있다.

 

의사코드 문법을 몇가지 알아보자.

의사코드 문법