[개인 공부] 알고리즘 공부(시간복잡도, 기본적인 알고리즘 분석)

안녕하세요, HoonIOS입니다.

저번시간에는 기초적인 알고리즘 개념과 알고리즘 평가하는 기준에 대해 알아봤는데요

 

만약에 못보셨다면 여기 들어가서 한번 글읽어보시는걸 추천드려요~!

 

이번 챕터에는 시간복잡도 분석, 선형 시간 알고리즘, 선형 이하 알고리즘, 이진 탐색 알고리즘에 대해 알아보겠습니다.

 

알고리즘의 시간 복잡도

- 우선 제일 기본적인 개념으로는 말그대로 알고리즘의 프로그램에 의해 컴파일 되었을때 걸린 시간이라고 할수 있습니다.

-  알고리즘의 시간복잡도인 알고리즘의 속도를 비교하기 위해 가장 직관적인 방법은 각각 프로그램으로 구현한뒤 같은 입력으로 두 프로그램의 수행 시간을 측정한는 방법이 있습니다.

- 근데 위 방법으로 구한 프로그램 수행시간이 알고리즘의 속도의 기준이 되기에는 매우 부적합하다. 그 이유를 아래에 말씀 드리겠습니다.

1. 가장 큰이유로 4가지가 있는데 그 이유로는 사용한 언어( 이거는 전 포스팅에서도 말씀 드렸어요 ㅎㅎ), 하드웨어, 운영체제, 컴파일러까지 수많은 요소로 인해 알고리즘 컴파일 시간은 많이 바뀔수 있습니다.
2. 두번째 이유로는 어떤 문자열을 구현했는지에 따라 바뀔수 있습니다. 어떤 문자열을 구현했고 어떻게 넘겨줬는지, 예를 들어 배열, 문자열같이 어떻게 문자열을 구현했는지 같은 경우가 있습니다. 위에서 본것처럼 사소한 문제에 따라 최종 수행 시간은 크게 달라 질수 있습니다.
3. 세번째 이유로는 실제 수행시간이 다양한 입력, 입력 크기에따라 실행시간이 변한다는것인데요, 이말은 즉 입력을 어떻게 했는지에 따라서 실행시간이 변한다는것 입니다.

그러면 수행시간을 어떤 기준으로 측정을 해야겠는지 의문이 생기시죠? 이제 한번 알아보겠습니다.

- 알고리즘에서 수행시간을 지배하는것은 반복문이다. 반복문의 예로는(for문, while문, do~while문이 있습니다.)

- 그렇지만 반복문이 모든 알고리즘을 지배한는 것은 아닙니다. 입력의 크기가 작을때는 즉 반복문이 조금 돌때는 반복문보다 다른부분에서 수행시간을 갖는 비중이 크겠지만, 입력의 크기가 커지면 커질수록, 반복문 알고리즘이 수행시간을 지배합니다.

- 따라서 입력의 크기가 거질수록 알고리즘의 수행시간은 배열의 크기 N에 따라 변한다고 생각하면 됩니다.

- N번 수행되는 반복문이 두개 겹치면 즉, 아래 예시처럼 for문이 두개가 겹치는 이중포문이 발생하고 안에 for문과 밖에 for문이 N번 만큼 실행되면 알고리즘 수행 시간이 N^2이 되는것을 볼수 있습니다.

for(int i = 0; i <= N; i++) {
	for(int j = 0; j <= N; j++) {
    <코드>
    }
}

- 그렇지만 2중 포문이 있다고 다 N^2이 되는것은 아닙니다. 다른 예를 살펴보겠습니다.

for(int i = 0; i <= N; i++) {
	for(int j = 0; j <= 100; j++) {
    	<코드>
    }
}

- 위같은 예제의 포문을 보면 한개는 N번 수행이 되고 다른 한개는 100번 수행이 되는것을 볼수 있습니다. 따라서 위 코드의 수행 횟수는 N+100이 되는것을 볼수있는데 이것은 N이 커질수록 100번 수행되는 반복문이 차지하는 비중은 줄어드는것을 볼수 있다. 

따라서 위 코드의 알고리즘의 수행시간은 N이라고 할수 있습니다.

(이 내용은 추후 좀더 자세히 다루어보도록 하겠습니다. 만약 업데이트 하면은 여기다가 링크 걸어 놓겠습니다 :) )

 

선형 시간 알고리즘

- 선형 시간 알고리즘에 들어가기 전에 쉽게 접근하기 위해 하나만 알아두면은 편합니다. 바로 입력 N이 두배 커지면 실행시간도 두배 길어지는 것을 말한다. 즉 입력과 실행시간은 정비례한다고 생각하시면됩니다.

- 위 내용을 보시면 선형시간 알고리즘을 왜쓰지? 라고 생각을 하실수 있지만 만약 입력이 작은 알고리즘은 다른 알고리즘보다 빠르게 해결할수 있다는것을 알수 있습니다.

y=n 함수

선형 시간 이하 알고리즘

- 선형 시간 이하 알고리즘이란 예를 들어서 A라는 남자 아이돌이 코를 성형했다고 치고 만약 이 아이돌의 코 성형 하기 전 날짜가 궁금해서 검색을 해 60만장 정도 되는 코성형 한 날짜 찾는다고 한다면 우리는 사진을 찾을때 하나하나 들어가서 모든 날짜를 들어가 볼 필요가 없다.

어떻게 하는게 효율적인지 한번 생각해 보고 아래 글을 보시는걸 추천드려요!

 

- 우선 정답은 중간쯤 날짜를 보고 그 사진이 성형을 했는지 않했는지 확인을 하고 만약 했으면 중간날짜부터 앞날짜 까지의 반을 만약 성형이 되있으면 중간부터 끝 날짜의 중간을 기점으로 체크를 해보는 식으로 1이 될때까지 나눠서 찾으면 된다. 즉 이런 방법을 선형 시간 이하 알고리즘이라고 합니다.

 

- 즉 간단히 설명하면 N이라는 경우를 계속 절반으로 나눠서 1이하가 될때 까지 몇번이나 나눠야 하는지 알수 있는데 바로 이렇게 나타내는 함수가 바로 로그입니다.

- 매번 절반씩 나누니깐 밑이 2인 로그 log2(밑이 2인 로그)를 사용하면 됩니다.

- 앞으로 우리는 log2(밑이 2인 로그)를lgN이라고 하겠습니다.

- 간략히 말하자면 Log함수는 굉장히 느리게 증가하는 함수입니다.

- 굉장히 느리게 증가하기 때문에 입력크기가 클때 장점이고 입력크기가 작을때는 선형 시간 알고리즘보다 오래걸린다는게 단점이라고 할수있다.

- 위 내용 때문에 선형 시간 이하 알고리즘은 입력의 크기가 커지는것보다 수행시간이 느리게 증가하는 알고리즘을 뜻합니다.

로그 함수

-위 그래프를 보면 x는 입력값이고 y는 실행 시간이라고 볼수 있습니다.

 

이진 탐색

- 이진 탐색은 이진 검색 알고리즘이라고 하는데 처음에 임의의 값으로 중간의 값을 선택하여 크고 작음을 비교하여 정렬하는 방식을 말한다.

- 따라서 이진탐색은 위에서 말한 선형 시간 이하 알고리즘하고 같은 것으로 위에서 선형시간 이하 알고리즘은 이진탐색이라고 부릅니다.

- 이진 탐색은 잘알아 두는게 좋다, 왜냐하면 유용하게 쓰이기 때문입니다.

 

 

지금까지 간단한 알고리즘하고, 시간 복잡도에 대해 알아봤는데요ㅎㅎ 공부를 하면서 복잡하고 이해 안된 부분이 있는데 이런부분은 더 알아 가야될꺼 같다고 생각합니다 :)

 

공부하면서 필요한부분이 있으면 계속해서 피드백 하겠습니다 글 읽어주셔서 감사합니다.

 

다음시간에는 몇가지 기본적인 알고리즘을 좀더 살펴보고 양이 괜찮으면 점금적 시간표시인 O표시에 대해 알아보겠습니다.