코드스테이츠 소프트웨어엔지지어링 부트캠프 +43일, 시간복잡도 공부

오늘 한 것

• 시간복잡도 공부
• 알고리즘,코플릿 복습

코플릿, 기본적인건데 계속 못품..

• Underbar 스프린트 : slice(), map(), filter()등등 배열 내장 메소드를 만들어 메소드들이 어떻게 callback 함수를 활용하는지 학습할 수 있었음.
• 콜백함수 : 고차함수의 인자로 전달되는 함수

  ---

시간복잡도에 대하여

시간복잡도 : 알고리즘의 성능 설명

• 알고리즘의 실행시간 : 컴퓨터가 코드를 실행하는 시간에 의존하는데, 이는 컴퓨터의 처리속도, 사용된 언어의 종류, 컴파일러의 속도에 의해 결정된다.
  • 입력값의 크기에 따라 알고리즘의 실행시간을 검증해볼 수 있음
  • 입력값의 크기에 따른 함수의 증가량(성장률)을 통해 알 수 있다. 이때 중요하지 않은 변수등의 데이터를 제거하면 실행시간에서 중요한 성장률에 집중할 수 있다.

빅오(Big - O) 표기법

빅오 표기법은 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다.

빨간색에 가까울 수록 horrible, 노란색은 fair, 초록색은 excellent 이다.

다음은 시간복잡도의 문제해결 단계를 나열한 것이다.

https://blog.chulgil.me/algorithm/

시간복잡도를 구하는 방법

시간복잡도를 구할 때 중요한 요소와 규칙이 있다.

• 반복문
• 조건문
• 재귀호출

규칙

1. 시간복잡도에서 상수값은 무시된다
2. 실제 개발자가 짜 놓은 코드를 수행하는 것은 상수 시간으로 간주한다.

예시

1. 아래 코드의 시간복잡도는 O(n) 이다. 간단히 코드를 n번 반복했기 때문이다.

function func(n){
    //짝수값 마다 코드 수행
     if(n%2===0)
     for(let i = 0;i<n;i++){
    
     }
    }

 

2. 아래 코드는 n*n번 수행하기 때문에 시간복잡도가 O(n^2) 이다.

function func(n){ 
	(let i = 0;i<n;i++){ 
    	for(let j = 0;j<n;j++{ 
        	//필요한코드 아무거나 
            } 
      } 
}

 

 

3. 다음 재귀 함수는 O(logN)이다.

function func(n){
      if(n==0){
      return n
      }
      func(n/2)
     }

여기서부턴 조금 계산이 어려워진다.

재귀 함수가 나올 때 공식의 모습은 함수 공식 안에 함수 공식을 또 호출하는 모양이 나온다.

그래서 위 예시의 함수는 f(n)=f(n/2)+C이다. (C는 조건문 처리시간)

이를 일반화 하면 f(n)=f(n/2^k)+C가 된다.

 

수식을 쓰기 귀찮고, 고등학교 수학이 많이 필요한 부분이라 캡쳐한다.

아래 이미지에 적혀있는 이유로 O(logN)의 시간복잡도를 갖는다.

---

 

참고자료 

https://pizzasheepsdev.tistory.com/3

https://blog.chulgil.me/algorithm/