Skip to content

Latest commit

 

History

History
92 lines (60 loc) · 5.04 KB

220406.md

File metadata and controls

92 lines (60 loc) · 5.04 KB

The Art of Computer Programming

연습한 cpp

딥러닝과 머신러닝이란?

  • 어떤 작업이 주어졌을 때, 컴퓨터가 작업(task)을 해결하는 방법.
    • 그래서 우리가 필요한 것.
    • 여러개의 해결 방법(Algorithm) 중에서, 최적화된 하나를 선택.
    • 최적화의 기된 알고리즘의 기준
      1. 시간(동작 속도)
      2. 공간(메모리) ... 보통 메로리보단 속도를 선택하는 추세긴함..

How to mesure running speed of Algorithm?

  1. 같은 입력에 대해 두 프로그램의 수행 시간을 측정함.

    • 하지만 이는 정확하지 않음.
    • reason => 수행시간을 결정하는 요인이 너무 많기 때문, (사용언어, 하드웨어, 운영체제, 컴파일러 등등..)
    • result => 알고리즘은 항상 같은 속도로 동작하는 것이 아니며, 입력의 크기나 특성에 따라 수행시간이 달라질 수 있다.

  2. 알고리즘 수행시간의 정확한 측정 기준

    • 알고리즘의 수행시간은 반복문이 지배한다(dominate) => 제일 영향이 크다.

선형시간 알고리즘(Sublinear time Algorithm)

  • 특히 이동 평균 계산에 유용하게 쓰인다.

선형 이하 시간 알고리즘

  • 입력의 크기가 커지는 것보다 수행시간이 느리게 증가하는 것이 특징이다

    • 수행시간의 증가율이 느릴 수록 좋은 알고리즘

  • 이진 탐색 알고리즘

  • 지수 시간 알고리즘

  • 다항 시간 알고리즘

    • 대부분의 알고리즘이 다항 시간 알고리즘에 해당한다.

시간 복잡도(Time complexity) O

  • 알고리즘의 수행 시간을 나타내는 척도이며, 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 수치이다.
    • 이때, 기본적인 연산은 "최소크기 연산을 나타냄"
  • 쉽게 생각해서 시간 복잡도의 기울기 변화율이 클 수록 입력 대비 평균 수행시간이 늘어난다고 생각하면 될 듯..?

그렇다면, 시간복잡도는 어떻게 계산하나요?

  • 코드 내에 반복문을 기준으로 최소 크기의 연산을 찾아, 입력 대비 수행시간에 대한 함수를 계산해 나타낸다.
  • 점근적 시간 표기 : O 표기
    • 시간 복잡도를 알고리즘의 수행시간을 표기하는 과정에서 생긴 단점을 보안해준다.
    • 어떻게?
    • => 상수부분 무시, 반복문의 반복수만 고려해서 나타내줌 => Big-O Notion
    • reason of using Big-O Notion => 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다버려, 간결하게 시간 복잡도를 표현할 수 있다.
      • 흠... 내 생각엔 함수 기울기 변화율을 그 자체를 의미하므로, 너무 대략적인 예측이 가능하다는 단점이 커, 알고리즘 사용 방식에 따라 조심해서 사용해야 할것같다.

Big-O Notion의 다양한 표현법

  • 상수와 같은 차수를 포함하는 시간복잡도, O(1) => 상수시간[constant-line]을 의미
  • 최고 차항의 개수가 둘 이상일 경우, 모든 최고차항을 포함해 표기 ex) O(N^2M + NM^2) // 최고차항 N과 M을 둘 다 표기

Big-O Notion 중 가장 아름답다고 생각한 부분,

  • Big-O Notion은 함수의 상한을 나타낼 수 있는 것이 가장 가치있다고 생각한다.
    • reason => N에 대한 함수 f(N)이 주어질 때, f(N) = O(g(N)) 임이 나타내는 것은,
    • 아주 큰 N과 C(N[0], C > 0)를 적절히 선택해준다면,
    • N <= N 인 모든 N에 대해 |f(N)| <=C*|(g(N)|이 참이 된다.
      • 즉,|f(N)| <=C * |(g(N)|이 성립하는 N과, C가 존재한다는 점이다.
      • 아 물론, N과 C는 단 하나만 존재하는 상수가 아니므로, 해당값이 일치하는 함수에서 직접 대입해 찾아야 한다는 점은 불편할 수 있겠지만,
      • 이를 활용해 대략적인 시간 복잡도 표현이 가능하며.. 이는 다양한 알고리즘 풀이 경험을 통해 직관적으로 예측할 수 있는 하나의 공식이 있다는 것이 Big-O Notion 표현법이 갖는 가장 아름다운 의의라고 생각한다.

추가로 공부한 알고리즘 관련 내용들

  1. 선택 정렬 알고리즘 구현(selection sort)
  2. 시간 복잡도의 분할 상환 분석 // 하지만 해당 내용은 문제에 따라 더 다양한 시간 복잡도 예측이 가능하다는 정도로 언급되어, "알고리즘의 정확한 시간 복잡도 예측이 필요할 때 사용할 수 있는 수단" 중 하나 정도로 알고 있다.
  3. 그렇다면, 어떻게 직관적으로 알고리즘의 수행 시간을 예측할 수 있는가?

    입력의 크리를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한을 초과할 가능성이 있다.

    책의 작가분께서는 추가로, 이는 대략적인 예측에 불과하며, 많은 경험을 쌓아 자신만의 직관을 만드는 것 또한 중요하다고 언급했다.