[알고리즘 1] 추상 자료형과 알고리즘 개념

 추상 자료형과 알고리즘 개념  

추상 자료형

• 자료형을 정의하려면 구체적으로 구현하기 전에 자료형에 대한 자료의 특성, 연산자, 연산자가 무엇을 수행하는지 등 자료와 연산자의 특성을 논리적으로 추상화하여 정의한 자료형을 추상 자료형이라 한다.

• 추상화는 “무엇(What)인가?”를 논리적으로 정의합니다.

• 구체화는 “어떻게(How) 할 것인가?”를 실제적으로 표현합니다.

잘 알려진 추상 자료형에는 복소수, 리스트, 스택, 큐, 맵, 우선순위 큐, 집합 등이 있습니다 .

알고리즘이란?

주어진 문제해결 방법을 추상화 하여 단계적 절차를 논리적으로 기술해 놓은 명세서입니다.

예시 ) 햄버거를 만드는 법

            집에서 직장을 가는 방법

햄버거를 만들기위한 재료를 준비하여 요리 순서를 진행하고 , 집에서 직장까지 가장 가까운 길을 찾는것 이 모두 알고리즘입니다 .

알고리즘의 조건

• 입력(Input)은 알고리즘 수행에 필요한 자료가 외부에서 입력으로 제공될 수 있어야 합니다.
• 출력(Output)은 알고리즘 수행 후 하나 이상의 결과를 출력해야 합니다.
• 명확성(Definiteness)은 수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어들은 명확하게 명시되어야 합니다.
• 유한성(Finiteness)은 알고리즘은 수행 뒤에 반드시 종료되어야 합니다.
• 효과성(Effectiveness)은 알고리즘의 모든 명령어들은 기본적이며 실행이 가능해야 합니다.

알고리즘 성능분석 방법

• 시간 복잡도는 알고리즘을 프로그램으로 실행하여 완료하기 까지의 총 소요시간입니다.
  시간 복잡도 = 컴파일 시간 + 실행 시간

• 컴파일 시간은 프로그램마다 거의 고정 적인 시간 소요를 말합니다 . .

• 실행 시간은 컴퓨터의 성능에 따라 달라질 수 있으므로 실제 실행시간 보다는 명령문의 실행 빈도수에 따라 계산입니다.

• 함수의 상한을 나타내기 위한 표기법으로 최악의 경우에도 수행 시간 안에는 알고리즘 수행 완료를 보장합니다 .