# CHAPTER 5 자료구조 - 복잡도

금성·2022년 11월 28일
0

CS 전공지식 노트

목록 보기
17/19

SECTION 5.1 복잡도

알고리즘의 효율성을 판단하기 위한 지표 중 하나

복잡도를 더 잘 쉽게 이해하기 위해서 자료 구조와 알고리즘을 먼저 알아봐야 한다.


.1 자료 구조 정의

데이터 값의 모임, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것.

책장으로 예를 들자. (출처 : https://bnzn2426.tistory.com/115 )

  • 가장 많은 책을 넣는 방법은 규칙없이 다 꽂아 넣는 것. -> 당장은 이 책장의 공간을 잘 활용한것 같아보임. 하지만 이후 책을 찾을때 문제 발생
  • 규칙이 없기 때문에 모든 범위에서 책을 찾아야함.

일정 규칙을 세워 보자. - 오름차순으로 정리

  • 책의 제목을 오름차순으로 꽂아 넣는다는 규칙을 세움 -> 책을 찾기가 수월해짐.
  • 공간도 모두 활용 할수 있음 -> 단, 처음 책을 꽂을때, 이후 추가할때 어려움 발생.

일정 규칙을 세워 보자. - 분야 별로 정리

  • IT 관련 서적만 찾아볼 수 있게 됨. 하지만 IT관련 서적이 더 있지만 들어갈 공간이 없음
  • 반면 소설이 꽂혀있는 라인은 공간이 여유로움
    => 공간의 비효율이 발생하기 시작

일정 규칙을 세워 보자. - 가림막

  • 가림막을 이용해 남은 IT관련 서적을 꽂음 -> 공간을 효율적으로 사용함
  • 하지만 가림막이 불필요한 공간을 차지함
  • 같은 분류가 밑으로 넘어가 버린 책은 헷갈림이 발생할 가능성
  • 책장과 책은 컴퓨터 세상에서 메모리와 데이터로 비유

    • 책장 = 메모리
    • 책 = 데이터
      => 디테일은 많이 다를 수 있지만 전체적인 개념을 이해하는데 무리가 없음

    연산에 사용되는 컴퓨터의 메모리 자원은 매우 한정적인데 반해 처리해야 할 데이터는 무수히 많을 것 -> 메모리 공간을 효율적으로 사용 해야함!

    그래서 필요한것이 자료 구조!

    • 자료 구조를 목적에 맞게 사용
      • 모든 목적에 맞는 자료구조는 없고, 어디에 어떤 자료구조를 써야할지 정답은 없음. 따라서 각각의 자료 구조가 갖는 장점과 한계를 이해하고 알고 사용하는것이 중요함.
      • 위의 간단한 예시에서도 다양한 이유와 목적으로 책들을 진열하는 방법을 제시했고 어떤 방법을 사용하든 정답은 없었음

    단, 자료 구조에서는 메모리 공간과 실행 시간의 효율성을 따져야만 함 !


.2 알고리즘 ( Algorithm )

알고리즘 : 어떤 문제를 해결하기 위한 일련의 절차나 방법을 공식화한 형태로 표현
=> 문제풀이에 필요한 계산절차, 처리과정의 순서

위의 예를 다시 생각해보자.

알고리즘은 책장에 진열된 책들을 어떤 순서나 규칙을 가지고 찾을 지에 대한 방법

  • 알고리즘의 조건

    • 입력 : 외부에서 제공되는 자료가 0개 이상 존재
    • 출력 : 적어도 2개 이상의 서로 다른 결과를 출력 (즉 모든 입력에 하나의 출력이 나오면 안됨)
    • 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성
    • 유한성(종결성) : 유한 번의 명령어를 수행 후(유한 시간 내)에 종료
    • 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것
  • 좋은 알고리즘의 분석 기준

    정확성 : 적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단.

    작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정

    기억 장소 사용량 : 수행에 필요한 저장 공간

    최적성 : 그 알고리즘보다 더 적은 연산을 수행하는 알고리즘은 없는가? 최적이란 가장 '잘 알려진' 이 아니라 '가장 좋은'의 의미이다

    • 복잡도
      - 시간 복잡도
      - 공간 복잡도

.3 복잡도

  • 공간 복잡도

    • 특정 크기의 입력에 대해 얼마나 많은 메모리를 차지하는지 의미
    • 알고리즘을 위해 필요한 메모리의 양
  • 시간 복잡도

    • 특정한 크기 입력에 대한 알고리즘이 얼마나 오래걸리는지 의미
    • 알고리즘을 위해 필요한 연산의 횟수
    • 복잡도를 표현하기 위해 점근 표기법중 빅오 표기법 사용
      => 알고리즘의 실행 속도!!


.4 점근 표기법

점근 표기법 : 함수를 단순화하여 함수의 증가율을 다른 함수와 비교 표현 하는 방법

  • 점근적 표기법에서 헷갈리지 말아야 할 것

    증가율이 더 빠르다 = 알고리즘이 더 느리게 수행된다.
    증가율이 더 느리다 = 알고리즘이 더 빠르게 수행된다.

    • 빅 - 오 : O(g(n)) 는 g(n)이라는 함수보다 증가율이 같거나 더 느린 함수들의 집합
    • 빅 - 세타 : θ(g(n)) 는 g(n)이라는 함수와 증가율이 같은 함수들의 집합
    • 빅 - 오메가 : θ(g(n)) 는 g(n)이라는 함수보다 증가율이 같은 함수들의 집합

    먼저, T(n) = n²+3n+1 로 예시를 들어보자

    T(n) = n²+3n+1 인 시간 복잡도를 n² 와 3n+1로 나누어 그래프로 나타내면

    n값이 증가할수록 3n + 1의 값이 전체 시간 복잡도에 끼치는 영향은 미미하게 됨
    n에 값이 무한히 증가할수록 n²+3n+1 그래프와 점근적으로 가까워짐

    즉, n에 값이 증가할수록 최고차항 이하의 값들은 함수 증가율에 큰 영향 X

    이를 토대로 알고리즘을 비교한다고 가정

    알고리즘 1 - T(n) = 10000n +20000
    알고리즘 2 - T(n) = n²+3n+1

    둘중 어느 알고리즘이 효율적인지 한번에 판단하기는 어려움 그래서
    => 이를 빅오로 표현하면 다음과 같음

    알고리즘 1 - T(n) = O(n)
    알고리즘 2 - T(n) = O(n²)


    • 빅오 표기법 (Big-O notation)

      F(n) = O(g(n))
    • 이 때 함수 g(n)을 함수 f(n)의 점근적 상한 이라고 함.
      • 즉, f(n)의 복잡도는 최악의 경우 g(n) 보다 작거나 같다는 의미. f(n) ≤ g(n)

    알고리즘 성능이 최악의 경우라도 g(n) 이상이라는 의미

    • 빅 오메가 표기법 ( (Big-Ω notation )

      F(n) = Ω(g(n))
    • 이때 함수 g(n)을 함수 f(n)의 점근적 하한 이라고 함.
      • 즉, f(n)의 복잡도는 최선의 경우 g(n)보다 크거나 같다는 의미 f(n) ≥ g(n)

    알고리즘 성능이 아무리 빨라도 g(n) 이하라는 의미

    • 빅 세타 표기법 ( Big-Θ notation )

      F(n) = Θg(n))
    • 이때 g(n)을 함수 f(n)의 점근적 상한 및 하한이라고 한다
      • 즉,f(n)의 복잡도는 최선이나 최악의 경우라도 g(n) 범위 내 존재 f(n) ≥ = g(n)

    알고리즘 성능이 g(n)의 상한과 하한에 포함한다는 의미

  • 각 표기법을 사용했을때 예시

    a. 시간 복잡도 최선을 고려했을 경우 - 하한 점근 ( 빅 오메가 )

    • 결과를 반환하는 데 최선의 경우 1초, 평균 1분, 최악1시간이 걸리는 알고리즘을 구현했다고 가정
    • 이 알고리즘을 100번 실행한다면, 최선의 경우 100초가 걸림
    • 하지만 실제로 걸린 시간이 1시간이 훨씬 넘겼다면?
      • 어디서 문제가 발생한건지 쉽게 알수 없음
    • 이 문제를 해결하기 위해 거의 대부분의 로직을 파악해야함
    • 따라서 최선의 경우를 고려했을때, 문제를 파악하고 해결하는데 많은 시간이 필요

    b. 시간 복잡도 중간을 고려했을 경우 - (빅 세타 )

    • 평균값을 기대하는 시간 복잡도로 고려
    • 알고리즘을 100번 실행할때 100분이 소요된다고 생각했으나,최악의 경우가 몇개 발생하여 300분이 넘게 걸림
    • 위 최선의경우를 고려했을 경우와 같은 고민을 안게됨

    c. 시간 복잡도 최악을 고려했을 경우 - (빅 오)

    • 극단적 예, 위와같이 최악의 경우가 발생하지 않는다는 가정은 제외
    • 최악의 경우를 고려하여 대비하는 것이 바람직
      => 가장 많이 쓰는 표기법

.5 자료구조와 알고리즘

위에서 이야기한 자료구조와 알고리즘, 복잡도의 정의와 서로의 상관 관계를 잘 이해해야 한다.

자료구조와 알고리즘은 서로 밀접한 관계를 가지고 있음

다시한번 책장에서 책을 찾는것을 예시로 들어 보자.

"클린코드" 라는 책장에서 찾으려고 한다.

  • ㄱ-ㅎ 제목순으로 진열 되어있다면 'ㅋ'이므로 뒤쪽부터 (역순)으로 찾게 될 것.
  • 책 분류별로 진열 되어있다면 IT관련서적 쪽을 먼저 찾게 될 것.

즉, 자료 구조의 선택 → 효율적인 알고리즘 선택

넓은 의미에서 자료구조 + 알고리즘(+@) = 프로그램

profile
내일부터 공부 해야지

0개의 댓글