본문 바로가기

나는 엔지니어/자료구조

시/공간 복잡도 우리가 프로그램을 판단하는 데에는 다음과 같은 몇 가지 기준을 바탕으로 한다. 1. 프로그램이 원래의 명세와 부합하는가? 2. 정확하게 작동하는가? 3. 프로그램을 어떻게 사용하고, 또 어떻게 수행하는지에 관한 문서(메뉴얼)화가 프로그램 되어 있는가? 4. 프로그램에서 논리적인 단위를 생성하기 위해 함수를 효과적으로 사용하는가? 5. 프로그램의 코드의 가독성이 좋은가? 6. 프로그램이 주기억장치화 보조기억장치를 효율적으로 사용하는가? 7. 작업에 대한 프로그램의 실행 시간은 받아들일 만한가? 프로그램의 공간 복잡도 프로그램을 실행시켜 완료하는 데 필요로 하는 공간의 양 ( 메모리 / 주기억 장치를 어느정도 사용하는가? ) 총 공간 요구 = 고정 공간 요구 + 가변 공간 요구 S(P) = c + Sр(I).. 더보기
순열 a,b,c가 존재한다고 가정할 경우순열의 집합은 다음과 같다.a,b,c a,c,bb,a,cb,c,ac,a,bc,b,a즉 총 6개의 순열이 나오는데 n개의 주어진 원소에 대해 n! 개의 상이한 순열이 있다는 것은 쉽게 알 수 있다.n! = n * (n-1) * ... * 1 네 개의 원소 {a,b,c,d}로 된 집합을 살펴보면 간단한 알고리즘을 얻을 수 있을 것이다.이것에 대한 순열의 집합은 다음과 같이 출력시키면 결과를 얻을 수 있다. 1) a로 시작하는 {b,c,d}의 모든 순열2) b로 시작하는 {a,c,d}의 모든 순열 3) c로 시작하는 {a,b,d}의 모든 순열 4) d로 시작하는 {a,b,c}의 모든 순열 ~로 시작하는 ~의 모든 순열 이라는 표현이 바로 순환의 실마리이다. 순열 n개에 대한 .. 더보기
선택 정렬 과 이진 탐색 .n >= 1 개의 정수를 정확하게 정렬한다. 배열을 이용한 선택 정렬 알고리즘.배열 정의 list[i] , 0 더보기
알고리즘 명세 알고리즘의 정의 : 특정한 일을 수행하는 명령어들의 유한 집합이며 다음과 같은 조건들을 만족해야 한다. 1) 입력 : 외부에서 제공되는 데이터가 0개 이상2) 출력 : 1개 이상의 결과를 생성한다.3) 명확성 : 각 명령들은 명확하고 애매모호하지 않아야 한다.4) 유한성 : 알고리즘의 명령대로 수행하면 어떤 경우에도 한정된 수의 단계 뒤에는 반드시 종료한다.5) 유효성 : 원칙적으로 모든 명령들은 종이와 연필만으로 수행될 수 있게 기본적이어야 한다. 더보기
기본 개념 참고 서적 : C로쓴 자료구조론참고 사항 : my think 모든 프로그램들은 시스템 생명 주기라 불리우는 개발 단계를 거친다.이러한 주기는 요구사항,분석,설계,코딩,검증 과정으로 구성되어 있다.이러한 과정이 독립적이라고 간주한다 할지라도 이 과정들은 상호 밀접한 관계를 가지고 있다. 1) 요구사항 ( 고객 미팅 )프로그래머에게 주어진 데이터 입력과 프로그래머가 생성해내야 하는 결과(출력)에 관한 정보를 기술한다.종종 이 초기 명세가 애매모호하게 정의되어 있는데 요구사항은 모든 경우에 대한 입력과 출력의 기술을명확하고 정밀하게 작성하여야 한다. 2) 분석 ( 요구 분석 )요구사항 단계가 끝나면 분석 단계가 시작된다.분석 단계에서는 각각의 문제(요구사항)들을 실제 다룰 수 있을 정도의 작은 단위들로 나눈다.. 더보기

티스토리툴바