728x90

알고리즘의 분석 : 시간 복잡도

- 알고리즘의 자원(resource)  사용량을 분석 , cf)자원: 실행시간, 메모리, 저장장치, 통신, 등
- 실행시간의 분석에 대해서 다룸

  • 시간복잡도(time complexity)

- 연산의 실행 횟수를 카운트(실행시간 은 실행환경에 따라 달라짐)
- 연산 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현
- 데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐 
   ex) worst-case analysis vs average-case anaysis :최악의경우 시간복잡도, 평균 시간복잡도 

  • 점근적(Asymptotic) 분석

-  Θ-, Ο-: n→∞일때 수행시간이 증가하는 growth rate로 시간복잡도로 표현

- 상대적으로 간단하고 실행환경에 비의존적이여서 가장 광범위하게 사용

  1. 상수 시간 복잡도 - 시간복잡도 : O(1) 

     ex) n개 데이터 배열 n/2 번째 데이터 반환

  2. 선형 시간 복잡도 - 시간복잡도 : O(n)

    ex) n개 데이터 저장된 배열 sum

    3. 순차 탐색 최악의 경우 - 최악의 경우 시간복잡도 : O(n)

    ex) n개 데이터 저장된 배열 target 있는지 검색

    2차식(Quadratic) : - 최악의 경우 시간복잡도 : O(n^2)

    ex) n개 데이터 저장된 배열 X, n개 데이터 저장된 배열 Y, X[i]=Y[j]의 경우 n(n-1)/2

  • 점근적(Asymptotic) 표기법

-  알고리즘 포함된 연산들의 실행 횟수를 표기하는 하나의 기법, 최고차 항 차수만으로 표시

-  가장 자주 실행되는 연산, 문장의 실행횟수를 고려

  1. Ο-표기 :: upper bound를 표현 

     ex) f(n) = 32n^2 + 17n^2 -32 , f(n) <= cg(n)

  2. Ω-표기 :: lower bound를 표현 : 오메가

    ex)  f(n) = 32n^2 + 17n^2 -32 , f(n) >= cg(n)

  3. Θ-표기 :: upper bound & lower bound를 표현 :세타

    ex) f(n) = 32n^2 + 17n^2 -32 , 0 <= c2g(n) <= f(n) <= c2g(n)
   Big-O 

 O(1)

O(log n) 

O(n) 

O(n log n) 

O(n^2) 

O(n^3) 

O(2^n) 

O(n!) 

 Constant

 Logarithmic

 Linear

 Log Linear

 Quadratic

 Cubic

 Exponential

 Factorial

  • 다항시간(polynomial-time) 알고리즘

다항식일 때 사용. 

저작자표시 변경금지

'For Real > 알고리즘' 카테고리의 다른 글

Backjoon1000_DrEngineer  (0) 2018.11.23
728x90

알고리즘 문제풀기 시작.

그냥 그렇다고하는거 시간을 재면서 써보니까 좋네^^



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Backjoon1000_DrEngineer
{
    public static void main(String[] args) throws IOException
    {
        //메모리 13024KB 시간:92ms
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String inputValue;
        String[] numbers = new String[2];
        while ((inputValue = bufferedReader.readLine()) != null)
        {
            numbers = inputValue.split(" ");
 
            System.out.print(Integer.valueOf(numbers[0]) + Integer.valueOf(numbers[1]));
        }
 
        /*        // 메모리 14408   112
        Scanner scanner = new Scanner(System.in);
        int A = scanner.nextInt();
        int B = scanner.nextInt();
        if (!(0 >= A || B >= 10))
            System.out.print(A + B);
        scanner.close();*/
        /*        // 메모리 14440 시간  112
        Scanner scanner = new Scanner(System.in);
        int A = scanner.nextInt();
        int B = scanner.nextInt();
        if (0 < A && B < 10)
            System.out.print(A + B);
        scanner.close();*/
    }
}



cs




저작자표시 변경금지

'For Real > 알고리즘' 카테고리의 다른 글

[권오흠 in 인프런] 영리한 프로그래밍을 위한 알고리즘 강좌- 기본  (0) 2019.01.02

+ Recent posts

티스토리툴바