시간복잡도(Time Complexity), 빅오(Big-O)표기법이란?

알고리즘
posted by 귀염둥이채원 2019. 2. 28. 02:38

# 시간복잡도(Time Complexity)란?

* 알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수

* INPUT N에 대하여 알고리즘이 문제를 해결하는 데에 얼마나 오랜 시간이 걸리는 지를 분석하는 것

* 최고차항의 계수만 표기하는 방법을 사용

  (N이 커질수록 낮은 차수들의 연산의 횟수는 상대적으로 작아져서 무시해도 됨)


ex) n개의 데이터에 대한 연산 횟수가 

2n^3-5n^2+n+1일 경우 시간 복잡도는 O\left(n^3\right)이다. 
최고차항의 계수 2와 -5n^2+n+1이 시간 복잡도에 영향을 안 끼치는 것은 아니나, 
전체적인 관점에서 보면 최고차항의 차수가 가장 큰 영향을 끼치고 그 외의 것들은 최고차항의 차수에 비하면 상대적으로 영향이 미미하기 때문이다.


# 알고리즘 성능 파악

1. 최선의 경우 Best Case

2. 최악의 경우 Worst Case

3. 평균적인 경우 Average Case


평균적인 경우가 가장 이상적으로 보이겠지만 알고리즘이 복잡해 질수록 평균적인 경우는 구하기가 매우 어려워 진다.

그러므로 최악의 경우로 알고리즘의 성능을 파악한다.


# 빅오(Big-O)표기법이란?

* 최악의 경우로 알고리즘의 성능을 파악하는 것

ex) Binary Search 알고리즘의 시간복잡도를 Big-O로 나타내면 O(n log n)

-> Binary 알고리즘은 n개의 원소가 있을때 아무리 못해도(최악의 경우에) 

   n log n번 정도(대략적) 반복문을 돌리면 값을 찾을 수 있다는 의미이다.


# 시간복잡도 정리

은 \log_{2}n을 의미한다.

  •  과 같은 상수(Constant) 형태
  • O\left(\log n\right) 과 같은 로그(Logarithmic) 형태
  • O\left(n\right) 과 같은 선형
  • O\left(n \log n\right) 과 같은 선형로그 형태
  • O\left(n^c\right), O\left(n^3\right)과 같은 다차(Polynomial) 형태
  • O\left(c^n\right), O\left(3^n\right)과 같은 지수(Exponential) 형태
  • O\left(n!\right)과 같은 팩토리얼(Factorial) 형태


\log n



시간복잡도가 O(N^3)이상이면 시간복잡도가 기하급수적으로 늘기때문에 실행하기 힘든 프로그램



# 참고사항

* 작성한 알고리즘이 1억 번의 연산을 하면 수행시간은 1초로 가정하고 접근하는것이 일반적이다.



# 참고 사이트

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84

https://namu.wiki/w/%EC%8B%9C%EA%B0%84%20%EB%B3%B5%EC%9E%A1%EB%8F%84

https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=220769859177&proxyReferer=https%3A%2F%2Fwww.google.com%2F

https://www.youtube.com/watch?v=OVRLHJC95Gs

https://www.youtube.com/watch?v=6Iq5iMCVsXA


'알고리즘' 카테고리의 다른 글

Segment Tree (구간 트리) ---- (작성중,,,,,)  (0) 2019.03.13
Parametric Search(파라메트릭 서치) 알고리즘 개념  (0) 2019.02.28
이진 탐색(Binary Search) 알고리즘 개념 및 예제 소스  (0) 2019.02.27

이클립스 단축키 정리

기타
posted by 귀염둥이채원 2019. 2. 27. 21:37

이클립스 단축키 정리입니다.



##########################################################

F1 : 도움말

F3 : 클래스, 메소드, 속성이 선언된 위치로 이동

F4 : 클래스의 계층구조 확인(Type Hierarchy view)

F5 : 디버깅 시 선택된 행의 메소드 내부로 이동 (Step In)

F6 : 디버깅 시 선택된 행의 아래로 이동 (Step Over)

F7 : 디버깅 시 실행중인 메소드 외부로 이동(Step Return)

F8 : 디버깅 시 다음 디버그 포인트(중단점)로 이동 (Resume)

F11 : 디버그 모드로 실행 (Debug)

F12 : Editor창으로 이동

 

##########################################################

Ctrl + / : 한 줄 주석(//) 처리 또는 해제

Ctrl + 콤마(,) 또는 점(.) : 다음/이전 에러(경고)로 이동

Ctrl + F6 또는 E : Editor 창 간의 이동 (파일간의 이동)

Ctrl + F7 : View 창 간의 이동 (Console, Problems 등)

Ctrl + F8 : Perspectives 창 간의 이동 (Java, Debug 등)

Ctrl + F11 : 실행 모드로 실행 (Run)

Ctrl + 1 : 빠른 수정 (에러에 대한 수정할 코드 추천)

Ctrl + D : 한 줄 삭제

Ctrl + F : 문자열 찾기 (Find/Replace 다이얼로그)

Ctrl + H : 문자열 찾기 (Search 다이얼로그)

Ctrl + I : 들여쓰기 자동 적용

Ctrl + K : 현재 선택된 문자열과 동일한 문자열 찾기

Ctrl + L : 행 번호를 입력하여 특정 행으로 이동 (Go to Line 다이얼로그)

Ctrl + M : 현재 View / Editor 를 최대화

Ctrl + N : 새로운 파일 / 프로젝트 생성

Ctrl + O : 메소드 또는 속성 이동

Ctrl + Q : 마지막으로 편집한 곳으로 이동

Ctrl + T : 클래스 계층 구조 팝업

Ctrl + W : 파일 닫기

Ctrl + Space : 코드 자동완성

 

##########################################################

Ctrl + Shift + F4 : 열린 파일 모두 닫음

Ctrl + Shift + Space : 메소드의 파라미터 목록 표시

Ctrl + Shift + B : 현재 행의 중단점(Break Point) 설정 / 해제

Ctrl + Shift + F : 코드 형식 정리

Ctrl + Shift + G : 선택한 메소드, 속성이 사용된 모든 곳을 검색 (Search view)

Ctrl + Shift + L : 모든 단축키 정보 표시

Ctrl + Shift + O : import 자동 추가 / 삭제

Ctrl + Shift + R : 파일(클래스 포함) 찾기(Open Resource 다이얼로그)

Ctrl + Shift + T : 클래스 찾기 (Open Type 다이얼로그)

Ctrl + Shift + X : 대문자 변환

Ctrl + Shift + Y : 소문자 변환

Ctrl + Alt + G : 전체 파일에서 선택된 문자열과 동일한 문자열 찾기 (Search view)

Ctrl + Alt + 화살표(up, down) : 현재 라인을 위(아래)로 복사

Alt + 화살표(up, down) : 현재 라인을 한 줄씩 위(아래)로 이동

'기타' 카테고리의 다른 글

2019년 7월 달력 다운로드 (엑셀O, 비번X)  (0) 2019.07.17
[미드] 왕자의 게임 시즌1~7 전편 다운로드 (한글자막O)  (0) 2019.05.27
윈도우10 정품인증 쉽게 따라하기  (0) 2019.05.27
블로그 소스코드 하이라이트: Colorscripter 및 SyntaxHighlighter  (0) 2019.02.28
URL Encoding 특수문자 코드  (0) 2019.01.29

이진 탐색(Binary Search) 알고리즘 개념 및 예제 소스

알고리즘
posted by 귀염둥이채원 2019. 2. 27. 21:28

# 이진 탐색(Binary Search)이란?

* 반씩 범위를 나누어 가면서 분할정복하여 탐색하는 방법

* 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘 (정렬된 데이터가 아니면 적용이 불가능)

* 사전을 찾을 때 사전을 펴서 찾는 단어가 없으면 위치에 따라 앞쪽을 찾거나 뒤쪽을 찾고, 찾을 때까지 그걸 반복하는 걸 생각하면 쉽다.

* 1부터 n까지 숫자중 하나 맞추기 게임을 생각하면 쉽다.


# 선형 자료구조의 대표적인 탐색 방법

* 선형탐색 (Linear Search)

처음부터 하나하나 비교하여 검색하는 방법

장점: 구현하기 쉽고, 정렬이 안되어 있어도 된다.

단점: 검색하는데 시간이 오래 걸린다.


시간 복잡도

최고: O(1), 평균: O(N), 최악: O(N)


* 이진탐색 (Binary Search)

장점: 속도가 빠르다.

단점: 값들이 정렬된 상태이어야 한다.


시간 복잡도

최고: O(1), 평균: O(log N), 최악: O(log N)


# 이진 탐색의 성능

* 탐색 대상의 범위 : 1/2 1/4, 1/16, ... (탐색 대상이 반씩 줄어들게 된다.)

* n : 데이터 집합의 크기

   x : 탐색 반복 횟수

   x = log2n

* 100만개의 데이터 집합 : 최대 20회

* 1000만개의 데이터 집합 : 최대 23회

* 4,294,967,296개(약 43억개)의 데이터 집합: 최대 32회


# 이진탐색 (Binary Search) 과정

1. 데이터 집합의 중앙에 있는 요소 선택

2. 중앙 요소의 값과 찾고자 하는 목표 값을 비교

3. 목표 값이 중앙 요소의 값보다 작다면 중앙을 기준으로 데이터 집합의 왼편에 대해 새로 검색을 수행

   크다면 오른편에 대해 이진 탐색을 새로이 수행

4. 찾고자 하는 값을 찾을 때까지 1번~3번 과정을 반복


# 예제 소스

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.io.FileInputStream;
import java.util.Scanner;
 
public class BinarySearch_Test {
    static int M; // 배열의 개수
    static int N; // 검색할 숫자의 개수
    static int input[];
 
    static void binarySearch(int input[], int low, int high, int searchValue) {
        // 값을 찾지 못한 경우
        if (low > high) {
            System.out.print("-1 ");
            return;
        }
 
        // 중간 index 구하기
        int mid = (low + high) / 2;
 
        // 1. searchValue < 중간값
        // 2. searchValue > 중간값
        // 3. searchValue == 중간값
        if (searchValue < input[mid]) {
            binarySearch(input, low, mid - 1, searchValue);
        } else if (searchValue > input[mid]) {
            binarySearch(input, mid + 1, high, searchValue);
        } else {
            System.out.print(+mid + " ");
            return;
        }
    }
 
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("C:\\java\\SW\\sample.txt"));
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
 
        for (int test_case = 1; test_case <= T; test_case++) {
            M = sc.nextInt();
            N = sc.nextInt();
            input = new int[M];
 
            for (int i = 0; i < M; i++) {
                input[i] = sc.nextInt();
            }
 
            System.out.print("#" + test_case + " ");
            for (int i = 0; i < N; i++) {
                int searchValue = sc.nextInt();
                binarySearch(input, 0, M - 1, searchValue);
            }
            System.out.println();
        }
        sc.close();
    }
}
cs


# 참고 사이트

https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89

https://www.youtube.com/watch?v=Vfg6-AWGsCw

https://ledgku.tistory.com/35

https://mygumi.tistory.com/72

https://blockdmask.tistory.com/167

https://wayhome25.github.io/cs/2017/04/15/cs-16/

'알고리즘' 카테고리의 다른 글

Segment Tree (구간 트리) ---- (작성중,,,,,)  (0) 2019.03.13
Parametric Search(파라메트릭 서치) 알고리즘 개념  (0) 2019.02.28
시간복잡도(Time Complexity), 빅오(Big-O)표기법이란?  (0) 2019.02.28

티스토리툴바