알고리즘 시간 계산 - algolijeum sigan gyesan

Question

안녕하세요. IT린이입니다. 오늘은 시간복잡도 계산 방법에 대해 알아보겠습니다.

제가 작성하는 시간복잡도 계산방법이란
코딩할 때, 시간복잡도 계산방법입니다.

시간복잡도를 처음부터 다잡고 가려면 각종 정렬 알고리즘부터 빅오, 빅세타, 빅오메가까지 설명이 길어지거니와
제가 학부시절 공학수학에서 배운 그래프까지 그려야하는 불상사가 발생합니다. 따라서 저는 '비전공자'분들을 위해 빠르게 시간복잡도를 계산하고 코딩을 할 수 있도록하는 방법에 대해 포스팅하겠습니다.

1. 시간복잡도란?

시간복잡도란 '해당 알고리즘이 걸리는 시간'을 의미합니다.
예를 들면 '2+2+2+2+2=10'보다 '2 x 5 =10'이 계산시간이 더 빠를 것입니다. 전자는 더하기라는 알고리즘을, 후자는 곱하기라는 알고리즘을 사용한 것입니다. 지금은 수가 작아서 차이가 안나지만 극단적으로

1,048,576+1,048,576+1,048,576+1,048,576+1,048,576 과
1024 1,048,576x 5 는 차이가 많이 나겠죠? (참고로 1,048,576는 2의 20승입니다)

이 시간복잡도는 컴퓨터의 CPU사용량에 영향을 미칩니다. 지금 Ctrl+Alt+Delete키를 눌러 작업관리자를 켜보세요.
프로세스 탭에서 CPU사용량을 볼 수 있을 것입니다. 현재 여러분의 여러 프로세스가 차지하고 있는 CPU사용량을 보실 수 있을 겁니다. 각 프로세스(그러니까 크롬, 인스타그램, 한글 2014와 같은 어플리케이션)들은 사용자의 CPU사용량을 줄이는 방법을 고안해서 출시하는 것이 중요합니다.

2. 시간복잡도 계산방법

시간복잡도를 표기하는 방법은 '빅오'표기방법을 씁니다.
예를 들어 다음과 같은 코드가 있습니다.

for(int i = 0; i < 1024; i++){
 for(int j = 0; j < n; j++){
   for(int d = 0; d < n; d++)
    for(int k = 0; k < n; k++
 }
}
for(int i = 0; i < 32; i++){
 for(int j = 0; j < n; j++){
  for(int d = 0; d < n; d++){
  }
 }
}

이 알고리즘은

라는 정확한 시간복잡도가 걸리는데요. 여기서 가장 높은 차수만 구해주면 됩니다. 따라서 빅오표기법으로쓰면

로 쓰면 되겠습니다! 즉, 가장 영향력이 높은 차수에서 상수부분을 제외한 값이 빅오표기법이 되겠습니다.

**참고 사항
상수 시간복잡도 부터 2의 n승 시간복잡도까지의 빅오표기법입니다.

3. 자료구조에 따른 시간복잡도

어떤 자료구조를 쓰느냐에 따라 이와같이 시간복잡도가 천차만별입니다. 예를 들면, 힙 자료구조를 사용한 코드입니다.

import heapq
def solution(n, K):
    answer = 0
    heapq.heapify(n)
    while len(n) > 0 and n[0] < K:
        x = heapq.heappop(n)
        y = heapq.heappop(n)
        scov_num = x + 2 * y
        heapq.heappush(n, n_n)
        answer += 1
        if len(n) == 1 and n[0] < K:
            return -1
    return answer

라는 코드가 있을 때, 시간복잡도는 O(NlogN)이 됩니다. 왜냐하면 힙 자료구조는 O(logN)이라는 시간복잡도이고 While문을 len(n) (==N)크기만큼 순환했기 때문에 N x logN이 됩니다

4. 마무리

시간복잡도는 어플리케이션 구축 시 필수로 고려되는 요소입니다. SQL쿼리문을 어떻게 짜느냐에 따라 DB 시스템 내 시간복잡도가 달라져 시스템을 최적화할 수 있고 코드을 어떻게 짜느냐에 따라 DB까지 메소드가 다녀오느냐, 아니면 바로 메소드 내에서 인자를 참조받느냐 등 최적화 요소가 존재합니다. 시간복잡도를 고려한 코드를 구현함으로써 더 좋은 개발자가 될 수 있다고 생각합니다.

감사합니다

-IT린이 올림

개발자/Algorithm

알고리즘 문제풀이 시간 복잡도 예상하기 및 시간 측정 방법

2021. 11. 25. 00:18

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

위 근사치를 이용하면 간단하게 입력의 크기와 제한시간으로 정답 알고리즘의 복잡도를 대략적으로나마 예측해 볼 수 있습니다.

문제에서 가장 먼저 확인해야하는 내용은 시간제한(수행시간 요구사항)입니다.

시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같습니다.

입력이 10,000,000 개의 경우: O(N) 알고리즘

입력이 50,000 개인 경우: O(N * log N) 알고리즘

입력이 10,000 개인 경우: O(N * N) 알고리즘

입력이 400개: O(N * N * N) 알고리즘

거꾸로 이야기하면 입력이 100개 이하라면 대체로 어떤 알고리즘을 써도 풀릴 가능성이 높고, 입력이 매우 작은 경우는 완전탐색으로도 문제를 풀 수 있을 가능성이 높다는 이야기겠죠.

Header: <ctime>
clock_t clock(void);
: clock() 함수는 프로그램의 실행 시작으로부터 경과된 시간을 clock ticks 수로 반환합니다.
단위는 clock tick이지만 ms와 동일합니다. 즉 ms단위를 정수형으로 반환합니다.
ctime에 정의되어있는 CLOCKS_PER_SEC과 같이 사용하면 sec(초) 단위로 출력할 수 있습니다.

더 정밀하게 측정하고 싶다면 chrono 라이브러리를 참고하세요.

clock_t 타입

ctime

Preview)

// 측정 시작 위치
clock_t startTime = clock();

/*
    측정할 코드
*/

// 측정 종료 위치
clock_t endTime = clock();

// 측정 시간 계산 (ms단위)
clock_t elapsed = endTime - startTime;

// Second로 변환
double timeInSecond = (double)(elapsed / CLOCKS_PER_SEC);

Example)

#include <iostream>
#include <ctime>    /* clock_t, clock, CLOCKS_PER_SEC */
#include <vector>

using std::cout;
using std::string;
using std::vector;

int main(void)
{
	vector<string> vec(100000, "bonjour");
	vector<string> tmp;

	// 시작 시간
	clock_t startTime = clock();
	
	// 시간 측정할 수행 코드
	for (vector<string>::size_type i = 0; i != vec.size(); ++i)
	{
		tmp.push_back(vec[i]);
	}

	// 종료 시간
	clock_t endTime = clock();

	// Millisecond
	clock_t elapsed = endTime - startTime;

	// Second
	double timeInSecond = (double)(elapsed / CLOCKS_PER_SEC); 

	cout << "Elapsed: " << timeInSecond << "s(" << elapsed << "ms)" << "\n";

	return 0;
}