자바로 배우는 핵심 자료구조와 알고리즘

상수 시간 : 실행시간이 입력 크기에 의존하지 않음. 요소를 읽고 쓰는 것
선형 : 실행시간이 입력의 크기에 비례
이차 : 실행시간이 n^2에 비례 (quadratic)

선택 정렬 (selection sort)

빅오 표기법 (big O notation)
O(1) - 상수 시간 알고리즘
O(n) - 선형 알고리즘
O(n^2) - 이차 알고리즘

증가 차수 (order of growth)
선형 알고리즘 차수 (Order of Linear Algorithm)

분할 상환 분석 (amortized analysis)
 - 일련의 호출을 하는 동안 배열을 복사하는 추가 비용이 분산되거나 분할 상환되었다.
 
검색엔진
    크롤링 (crawlling) - 웹페이지를 다운로드하고 파싱
        jsoup library 사용
    인덱싱 (Indexing) - 검색어를 포함한 페이지를 찾는데 필요한 자료 구조
    검색 (retrieval) - 인덱스에서 결과를 수집하고 검색어와 가장 관련된 페이지를 식별하는 방법

트리 탐색
    깊이 우선 탐색 (DFS : depth first search)
    스택 (stack)
        LIFO (last in, first out)
        ArrayList, LinkedList class 사용
        Stack class 사용
        ArrayDeque class (implements Deque interface)
    큐 (queue)
        FIFO (first in, first out)
    
    이진 탐색 트리 (BST : binary search tree)
        높이에 대한 노드 수 : n = 2^h - 1 (n:노드, h:높이)
        노드에 대한 높이 : log 2 n ＝ h
        실행 시간 : log n
        증가 차수 : O(log n)
        TreeMap은 레드 블랙 트리 사용

레디스 (redis : Remote Dictionary Server)
    server : RedisToGo site
    client : jedis

정렬 알고리즘
    기수 정렬 (radix sort)
    힙 정렬 (bounded heap sort)
    병합 정렬 (merge sort) : O(n log 2n)
    삽입 정렬 (insertion sort) : O(n^2)
    선택 정렬 (selection sort) : O(n^2)