실전 머신러닝 1장 머신러닝 개념/모델/시간&공간복잡도

머신러닝

-목적에 따라

 

지도학습: 입력 피처와 입력 피처에 해당하는 목표 변수의 쌍이 주어졌을 때

이 관계를 모델링하여 입력으로 들어온 새로운 피처로 목표 변수 예측

(분류,회귀 문제)

 

비지도학습: 피처 공간만 주어진 상태에서 학습하여 피처 공간의 분포를 모델링하고 인사이트 도출

(군집화, 이상값 탐지)

 

강화학습: 행동의 좋고 나쁜 정도를 학습 알고리즘에게 알려 주는 것

강화형 기계 학습의 대상이 되는 컴퓨터 프로그램을 에이전트(agent)라고도 한다. 에이전트는 주어진 상태에서 자신이 취할 행동을 표현하는 정책(policy)을 수립한다. 에이전트가 최대의 보상을 받을 수 있는 정책을 수립하도록 학습시키는 것이 강화형 기계 학습의 목표이다.[네이버 지식백과]

 

 

 

머신러닝 모델

 

지도학습 모델-선형 모델:

• 최소 제곱법
• 로지스틱 회귀
• 라쏘
• 릿지
• 엘라스틱 넷

지도학습 모델-트리 모델:

• 결정 트리
• 랜덤 포레스트
• 그레이디언트 부스팅
• 트리

지도학습 모델 - 기타:

• K-최근접 이웃
• 서포트 벡터 머신
• 다층 퍼셉트론

 

비지도학습 모델:

• K-평균 군집화
• 계층적 군집화
• 주성분 분석

---

시간 복잡도

 

✔Big-o 표기법

시간 복잡도란?

함수의 실행 시간을 표현

 

실행 시간이란?
함수/알고리즘 수행에 필요한 스텝 수 

 

 

점근적 분석
임의의 함수가 N -> ∞로 갈때, 어떤 함수 형태에 근접해지는지 분석
θ(N) -> 점근적 표기법

 

 

✔시간 복잡도 성능(빠름->느림)

• O(log n) > O (n) > O(n log n) > O(n^2) > O(n^3) > O(2^n) > O(n!)

✔상수 시간/함수 : O(1)

입력 자료와 연관된 연산 없이 탐색,출력,반환

 

✔선형 시간/함수: O(N)

n번의 반복문 루프 도는 경우

 

✔2차 시간/함수:O(N^2) , 3차 시간/함수:O(N^3)

삽입 정렬,버블 정렬,선택 정렬

큐빅, 삼중for문

 

✔지수 시간/ 함수: O(2^N)

피보나치 수열

 

✔로그 시간/함수:O(logn)

이진 검색, 퀵 정렬, 병합 정렬, 힙 정렬

https://ontheway.tistory.com/47: 참고

 

 

참고자료

 

 

공간 복잡도

공간 복잡도(Space Complexity)란, 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양

총 공간 요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있으며 수식으로는 S(P)=c+SP(n)으로 표기

 

https://madplay.github.io/post/time-complexity-space-complexity:참고

---