240110-TIL

1월 10일

 

오늘은 집 보일러가 고장나서 굉장히 추운 하루를 보냈다.

 

컴퓨터 앞에 앉아있는데 발이 너무 시려서 컴퓨터 본채가 따뜻하니 본채에 발을 대면서 공부했다.

 

그래서 이렇게 힘들게 공부해서 오늘 배운건 뭐냐?

 

BIG-O표기법

어제 알고리즘 세션에서 알고리즘이 무엇인가와

 

알고리즘 문제풀이에 자주 사용되는 배열,리스트,연결리스트에 대해 배웠다.

 

이렇게 열심히 배워서 알고리즘 문제를 풀었는데 내가 푼 알고리즘의 성능이 어떤지 어떻게 알 수 있을까?

 

프로그램의 평가 기준을 보자

• 원하는 결과의 생성 여부
• 시스템 명세에 따른 올바른 실행 여부
• 프로그램의 성능
• 사용법과 작동법에 대한 설명 여부
• 유지 보수의 용이성
• 프로그램의 판독 용이

우리가 알고 싶은것은 프로그램의 성능 부분이다

 

프로그램의 성능

성능 평가를 하기 위해선 우선

• 성능 분석 : 프로그램을 실행하는데 필요한 시간과 공간의 추정
• 성능 측정 : 컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간 측정

분석과 / 측정을 거쳐서 프로그램을 성능을 평가하게 된다.

 

시간과 공간이란 말이 나오는데 우리는 시간 복잡도와 공간 복잡도에 대해서 알아야한다.

 

벌써부터 머리가 지끈지끈 아파온다....

 

공간 복잡도(space complexity)

• 프로그램을 실행시켜 완료하는데 소요되는 총 저장 공간
• Sp = Sc + Se
  • Sc : 고정 공간
    • 명령어 공간, 단순 변수, 복합 데이터 구조와 변수, 상수를 말한다
    • 입력 크기와 무관하게 항상 필요한 공간
  • Se : 가변 공간
    • 크기가 변하는 데이터 구조와 변수들이 필요로 하는 저장 공간이다.
    • 런타임 스택(runtime stack)을 위한 저장 공간
    • 입력 크기에 따라 메모리 요구량이 달라진다.

 

시간 복잡도(time complexity)

• 프로그램을 실행시켜 완료하는데 걸리는 시간
• Tp = Tc + Te
  • Tc : 컴파일 시간
  • Te : 실행 시간
    • 단위 명령문 하나를 실행하는데 걸리는 시간
    • 실행 빈도수(frequency count)

 

이 시간복잡도와 공간계산법을 활용하여 이 프로그램이 좋은건지 아닌건지 표기해 주는게 바로?

점근식 표기법

• 주어진 알고리즘이 있을 때, 보다 간단한 함수로 만들어 표시하는 방법
• 입력 데이터의 크기에 따라, 수행시간 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시
• 연산의 실행 횟수는 입력 크기 n에 대한 함수료 표현된다
  • F(n) = n^2 + 3n + 1

 

그중에서도 Big-O (상한 표기법) - 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠이 가능한 녀석

 

후 여기까지 와야 드디어 Big-O에 대해서 적을 수 있다.

 

Big-O 표기법의 특징 이라 한다면

1. 상수항 무시 : Big-O는 데이터 입력값이 충분히 크다고 가정하고 있고(상한 표기법) 알고리즘의 효율성을

데이터 입력값의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다

 

ex)

O(2N) -> O(N)

 

2. 영향력 없는 항 무시 : 데이터 입력값의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항 이외의 영향력이 없는 항은? 개무시 해버린다.

 

ex)

•O(n^2 + 2N + 1) -> O(N^2)

 

 

 

 

Big-O 표기법에서 주로 사용되는 표이다.

 

그래프에 나와 있는 시간 복잡도의 성능을 비교하면 다음과 같은데

 

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^N)

(빠름 ------------------------------------------------------->느림)

 

Big-O 표기법의 예제

1. O(1) : 스택에서 Push, Pop

2. O(log n) : 이진트리

3. O(n) : for 문

4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

5. O(N^2): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)

6. O(2^n) : 피보나치 수열

 

 

오늘은 Big-O표기법에 대해서 정리해 봤다.

 

정리하면서 느끼는 것이지만 정말 지금도 확 와닿지 않는데

 

Big-O 표기법의 예제가 어떤 것들이 있고 알고리즘 문제들을 하나하나 풀어보다 보면 이해가 될 것 같다.

 

1월 10일 TIL은 여기서 마치도록 하겠다.