Lagifun's 정보 기록소

개론

 - '윤성우의 열혈 자료구조'를 공부하면서 필기한 내용들을 블로그에 요약정리

 - 복습 + 백업을 목적으로 둔다.

01-1 강의

     강의를 위한 서론. 패스.

01-2-1 강의

     1. 이상적 알고리즘   

     2. 알고리즘 평가요소 

           ㅡ 시간복잡도, 속도(cpu의 부담)

           ㄴ 공간복잡도, 메모리 사용량

        => 시간복잡도가 더 중요

                ex) 메모리는 썼다 지울 수 있다.(공간 감소)

                      하지만 메모리 사용을 위한 접근시간이 증가한다(시간 증가)

         ※ 시간복잡도>공간복잡도

3. 시간복잡도 평가법 

      ㅡ cpu가 처리하는 연산횟수(중심이되는 특정연산의 횟수) 측정(연산횟수 증가 = cpu사용량 증가= 시간증가 = 시간복잡도 증가)

      ㄴ 데이터수(x축)에 대한 연산횟수(y축)를 나타내는 함수 T(n)구성

       => 함수에 대한 그래프를 보고 한눈에 쉽게 알고리즘 비교가능

*주어진 상황과 요구되는 특성에 따라 알맞은 알고리즘을 선정하자.

01-2-2 강의

1.

중심연산자

주변연산자(의존전 연산자): 주변연산자의 연산횟수는 중심이 되는 연산자의 연산횟수에 의존적

ex) ==(중심)가 참을 반환할때까지 <, ++(주변)가 수행된다.

2.

시간복잡도 평가하기

1. 중심연산자 선택

2. 중심연산자를 기준으로 시간복잡도 함수 T(n) 생성(n은 데이터, T(n)은 연산횟수)

3. 알고리즘간 T(n)의 패턴을 비교, 분석한다

3.

T(n) ㅡ 최선: 어짜피 만족스러운 경우, 관심↓, ∴ 고려x  =>  (best case)

       ㄴ 최악: 문제가 되는경우, ∴ 시간복잡도의 기준  =>  (worst case)

       ㄴ 평균: 모든 상황을 고려한 평균을 구하기 힘듦 ∴ 보조적

4.

순차탐색 알고리즘

개념: 차례대로 배열을 검색하는 방식

T(n)=n(최악의 경우)

01-2-3 강의

평균적인 경우의 T(n) 구하기 ->요점정리 생략한다

01-2-4 강의

이진탐색 알고리즘

특징: 순차탐색보다 좋은 성능을 보인다.

조건: 배열에 존재하는 데이터는 (어떤 기준이던지) 정렬되어 있어야함.

개념

0. 오름차순으로 데이터가 정렬되어 있으면

1. 중앙값을 찾는다 -> 중앙값 = (배열인덱스 시작+끝)/2

      *배열인덱스 : 배열의 요소, /할때 몫은 버린다(c언어 구현할때 처럼)

2. 중앙값과 탐색대상을 비교

if 중앙>탐색   일시    처음~ 중앙-1    으로 반복검색

   중앙<탐색                  중앙+1~끝

※ 중앙값을 제외하는 이유

1. 이미 검색한 요소이다.

2. 데이터 수가 많을때 중복검색이 되면 = 계산시간↑

01-2-5 강의

실제 소스 구현, 28.p참조, 유의사항이 ☆로 2개있다. 필독.

01-2-6 강의

이진 탐색 알고리즘의 시간복잡도(최악일 경우)

1. 중심연산자 '=='

2. 32.p하단~33.p 상단 -(결과)- 데이터 n이 1이 될때까지 2로 나눈횟수k(비교연산)

    ㄴ n=1일때 마지막 비교연산

3. 위식에서 n과 k간의 관계는 n*(2^(-1))^k=1 -> n =2^k -> log2n=klog22

∴ k = log2n

4. T(n) = k+1 = log2n+1

5. 하지만 빅오표기법으로 인해 T(n) = log2n(정확히는 O(log2n)=>O(logn), 01-2-8참조)

=> +1을 제외하는 이유  1. T(n)함수에서 +1은 영향이 매우적다

2. 우리는 알고리즘 패턴을 통해 알고리즘의 시간복잡도를 분석하기때문에 패턴이 중요하다.

         =>빅오표기법을 참조하여 결정한다.

01-2-7 강의

1.

T(n)의 상수가 매우큰데 생략한다면?

-> 함수를 구성하는 상수가 나머지에 영향을 줄 정도로 크다면, 그 알고리즘은 사용하지 않는 것이 좋다.

ex) 1≤n≤10 T(n)=n²+1000 -> n=1일지라도 T(n)=1000이다. ∴ 애초에 비효율적이다.

2.

빅오표기법: T(n)에서 실제로 영향력을 끼치는 부분을 '빅오' 라고한다.

3.

단순하게 빅오 구하기 ㅡ '최고차항' 만 남기기

       ㄴ 최고차항의 상수제거(패턴을 보기때문에 상수는 무시한다.)

ex) n²+2n+1       -> O(n²)

     n⁴+n³+n²+1   -> O(n⁴)

     5n³                -> O(n³)

=> 단, 같은 차수의 알고리즘끼리 비교할시에는 상수를 고려한다.

∴ 이를 일반화하면 T(n) = a*n^m + b*n^(m-1) + ... + a₁  -> O(n^m)

4.

빅오의 종류 ㅡ 상수형 빅오: O(1), 이상적, 흔치않음

ex) 항상 2회만 진행되는 알고리즘이더라도 O(3)이 아닌 O(1)이다.

       ㄴ 로그형 빅오: O(logn), 일반적, 쓸만함

       ㄴ 선형 빅오: O(n), 좋지않음

       ㄴ 선형로그형 빅오: O(nlogn), 좋지않음

       ㄴ 지수형 빅오: O(n^m), 사용x

∴ 알고리즘을 만들시 지수형->로그형으로 만드려고 노력해야한다.

보고 타자만치는데도 한참걸리네...