시간복잡도와 공간 복잡도 이해

주요 시간 복잡도 & 성능

O(1) - Constant Time

인풋의 크기와 상관 없이 항상 일정한 시간 소요

function getFirstElement(arr) {
  return arr[0];
}

O(logn) - Logarithmic Time

로그 시간 복잡도 / Log(16) = 4
대표적인 구조로는 이진 탐색이 존재한다.

function logCounter(n) {
  let loopCount = 0;
  for(let i=2;i<n;i*=2) {
    loopCount++;
  }
  return loopCount;
}

logCounter(16) // 4

O(n) - Linear Time

선형 시간 복잡도, 인풋 증가에 비례
적어도 한번씩은 확인해야 하는 알고리즘에 사용됨

function countCharacters(str) {
  let count = 0;
  for (let i=0;i<str.length;i++) {
    count++;
  }
  return count;
}

O(n2) - Quadratic Time

2차 시간 복잡도, 인풋의 증가 시 n의 제곱 비율로 증가

function buildMatrix(arr) {
  let matrix = [];
  for(let i =0;i<arr.length;i++){
    matrix[i]=[];
    for(let j=0;j<arr.length;j++){
      matrix[i].push(arr[j]);
    }
  }
  return matrix;
}

O(n!) - Factorial Time

팩토리얼 시간 복잡도, 가장 느린 연산

function factorial(n) {
  let num = n
  if(n===0) return 1
  for(let i=0;i<n;i++){
    num = n*factorial(n-1)
  }
  return num
}

결론

• 최고차항만 표기한다.
• 상수는 포함하지 않는다.

그런데 이렇게 되면 실제로 정확하게 얼마나 시간이 걸릴지 계산하는 척도보단 얼마나 중첩되어져 있는지?
위의 그래프를 참고 정도 하는 정도가 될거 같고, 중첩된 반복문은 피해야 할거 같다.

샘플 코드

해당 코드에서 $template, $params 가 몇개냐에 따라 실행시간이 얼마나 걸리게 될까?

빅오 표기 법으로는 O(n*n) 이 될것이다.

중첩되어 있는 반복문이기 때문에 해당 경우는 $template, $params 의 갯수가 1~2 이상 늘어나면 비약적으로 실행 시간이 늘어나게 될거 같다.

$template = [];
$params = [];
foreach ($template as $key => $data) {
	foreach ($params as $param => $value) {
		$template[$key] = str_replace('{'.$param.'}', $value, $template[$key]);
	}

	if (isset($params['slug'])) {
		if (isset($template['template'])) {
			$template['template'] = $this->replaceUrl($params['slug'], $template['template']);
			$template['template'] = str_replace('{logo}', config('aws.s3_image_cloudfront_url').$this->request['logo'], $template['template']);
		}

	}
}

---

참조

[코딩문 유튜브 채널] https://www.youtube.com/watch?v=5Ky59iblLBI