Algorithm, Notation

algorithm : 특정 문제 해결을 위해 논리적으로 기술한 일련의 명령문
program : algorithm + data structure

알고리즘의 요건

1. 완전성과 명확성
   수행단계와 순서과 완전하고 명확해야 하고 지시한대로 실행하면 결과가 얻어 져야함.
2. 입력과 출력
   입력 : 알고리즘이 처리해야 할 대상으로 제공되는 data
3. 출력: 입력 data를 처리하여 얻은 결과
4. 유한성
   유한한 단계 이후에는 반드시 종료되어야 한다.ADL (Algorithm Description Language)
   알고리즘 기술을 위해 정의한 언어이며 사람이 이해하기 쉽고 프로그래밍 언어로의 변환이 용
   이하다.
   ADL 데이터 : 숫자, bool값, 문자
5. 알고리즘의 표현

ADL 명령문 : 지정문, 조건문, 반복문, 함수문, 입력문 …, 명령끝에는 ; 사용

1. 지정문 (assignment), 순차적 방식
   형식 : 변수 <- 식
   식 : 산술식, 부울식(결과 T,F 표현은 논리 연산자, 관계 연산자), 문자식
2. 조건문(condition), 선택적
   종류 : if문, case문

 

1. 반복문(repeat), 일정한 명령문 그룹을 반복하는 loop 형태
   종류 : while, for, do-while
   무한루프 1. while(true){ S } 2. for( ; ; ) { code }

while 문과 do- while의 차이

앞의 그림이 while, 뒤에 그림이 do-while ADL을 나타낸다. do- while은 조건문과 관계없이 S가 최소한 한번 실행된다.

4. 함수문
   형식: function_name(parameter) { code }
   호출 함수로의 복귀: return value;
   함수 호출 : funtion_name(argument);
   인자와 매개변수관계: call by value
5. 입출력문
   입력 함수 read, 출력함수 print

ADL 기술 규칙
◦ 함수의 입출력 변수를 명확히 명세
◦ 변수의 의미를 알 수 있게 정의
◦ 알고리즘의 제어 흐름은 되도록 순차적
◦ 시각적 구분을 위해 인덴테이션(indentation) 이용
◦ 코멘트는 짧으면서 의미는 명확히
◦ 함수를 적절히 사용

순환 (recursion)

1. n이 자연수이면 n+1은 자연수이다. 2. 자연수에는 이 외의 수는 없다.

순환의 종류

1. 직접순환 : 함수가 직접 자신을 호출 e.g) fibonacci (재귀로 표현할 때)
2. 간접순환 : 다른 제3의 함수를 호출하고 그 함수가 다시 자신을 호출

Factorial

1. 순환 함수로의 표현

   public static int factorial(int n) { if (n <= 1) return 1; else return n * factorial(n - 1); // 자기 자신을 다시 호출. }

2. 비순환 함수로의 표현

   public static int nFactorial(int n) { if (n <= 1) return 1; int fact = 1; for (int i = 2; i <= n; i++) { fact = fact * i; } //for문으로 해결 return fact; }

이원탐색

public static int binsearch(int[] a, int key, int left, int right) {
    if (left <= right) {
        int mid = (left + right) / 2;
        if (key == a[mid])
            return mid;
        else if (key < a[mid])
            return binsearch(a, key, left, mid - 1);
        else
            return binsearch(a, key, mid + 1, right);
    }
    return -1;
}

프로그램 성능 분석

평가기준

• 원하는 결과의 생성 여부
• 시스템 명세에 따른 올바른 실행 여부
• 프로그램의 성능
• 사용법과 작동법에 대한 설명 여부
• 유지 보수의 용이성
• 프로그램의 판독 용이

성능평가

성능 분석 (performance analysis)

• 프로그램을 실행하는데 필요한 시간과 공간의 추정

성능 측정 (performance measurement)

• 컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간 측정

공간 복잡도와 시간복잡도

공간 복잡도 (space complexity) ◦ 프로그램을 실행시켜 완료하는데 소요되는 총 저장 공간

• Sp = Sc + Se

Sc : 고정 공간 (명령어 공간, 단순 변수, 복합 데이터 구조와 변수, 상수)

Se: 가변 공간 (크기가 변하는 데이터 구조와 변수들이 필요로 하는 저장 공간, 런타임 스택
runtime stack을 위한 저장 공간)

시간 복잡도 (time complexity) ◦ 프로그램을 실행시켜 완료하는데 걸리는 시간

• Tp = Tc + Te

Tc : 컴파일 시간

Te : 실행 시간 (컴파일 시간은 정적인 반면 실행 시간은 가변이기 때문에 이 실행시간을 추정하여 성능평가로 대체) -> 우리는 실행 시간만을 가지고 성능평가를 하겠다.

 

실행 시간 추정요소
단위 명령문 하나를 실행하는 데 걸리는 시간

• 단위 시간으로써 일정하다고 가정
  단위 명령문 실행 빈도수(frequency count)
• 단위 명령문을 프로그램 단계(program step)로 간주
  → 성능은 프로그램 단계 실행 빈도수로 추정
  큰 자리 수(order of magnitude): 1, 10, 100

점근식 표기법

• Big-Oh (O) 상한기준
• Big-Omega (Ω) 하한기준
• Big-Theta (Θ)

Big-Oh (O), 상한 기준

수학적 정의 : f, g가 양의 정수를 갖는 함수일 때, 두 양의 상수 a, b가 존재하고, 모든 n≥b에 대해 f(n) ≤ a ∙ g(n)이면, f(n) = O(g(n))
즉, a값이 존재하면 빅오 표기법을 사용할 수 있다.

Big-Omega 하향 기준: f, g가 양의 정수를 갖는 함수일 때, 두 양의 상수 a, b가 존재하고 모든 n ≥ b에 대해 f(n)≥ a ∙ g(n) 이면, f(n) = Ω(g(n))

Big-Theta (Θ) 상한과 하한으로 한정: f, g가 양의 정수를 갖는 함수일 때, 세 양의 상수 a, b, c가 존재하고, 모든 n ≥ c에 대해 a ∙ g(n) ≤ f(n) ≤ b ∙ g(n) 이면, f(n) = Θ(g(n))

빅오표기법 특징

1. 상수항 무시
   O(3N + 5) -> O(N)
2. 영향력 없는 항 무시
   O(N^3 + 6N) -> O(N^3)

예제

public static void test(int [] testList) {
    for(int i = 0; i < testList.length; i++) {
        for(int j = 0; j < testList.length; i++) {
            System.out.println("*")
        }
    }
}

public static void test(int [] testList) {
    for(int i = 0; i < testList.length; i++) {
        for(int j = i; j < testList.length; i++) {
            System.out.println("*");
        }
    }
}

public static void test(int [] testList1, int [] testList2) {
    for(int i = 0; i < testList1.length; i++) {
        for(int j = 0; j < testList2.length; i++) {
            System.out.println("*");
        }
    }
}

public static void test(int[] testList1, int[] testList2) {
    for (int i = 0; i < testList1.length; i++) {
        for (int j = 0; j < testList2.length; i++) {
            for (int k = 0; k < 10000; k++) {
                System.out.println("*");
            }
        }
    }
}