👨‍🏫 들어가며!

안녕하세요! 강창민 튜터입니다. 오늘은 저번 시간보다는 다소 배워야 할 것이 있습니다만 긴장하지 마시고 찬찬히 따라오시면 됩니다!

오늘 배울 것은 뭐에요?

• 시간 복잡도에 대해서 배웁니다!
  • 프로그램의 수행 성능을 최악의 경우를 가정하여 정량화하는 방법이에요!
  • 시간 복잡도를 알지 못하면 내가 알고리즘을 고안해도 이 방법이 정말로 유용한지 판단하기 힘들어요!
• 공간 복잡도도 잠깐 살펴볼거에요!
  • 공간 복잡도는 시간 복잡도에 비해서 크게 중요하지는 않아요!
    • 물론, 공간도 최적화하면 당연히 좋습니다.
    • 하지만 최적화가 덜 되어있다고 해도 당장은 프로그램을 돌리는 컴퓨팅 리소스의 성능을 올리면 해결이 되어서 시간 복잡도에 비해서는 중요도가 높지 않아요! → 물론 나중엔 코드로 최적화를 해서 비용을 절감해야 좋은 개발자겠죠?
• 그리고, 알고리즘에서 자주 쓰이는 자료구조들에 대해서 알아볼거에요! 알아볼 자료구조들은 다음과 같아요!
  • 배열
  • 링크드리스트

시간 복잡도가 뭐에요?

<aside> 💡 시간 복잡도는 꼭 최악의 경우를 기준으로 계산하도록 하세요!

</aside>

• 정의

  • 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. (출처: 위키피디아)
  • 정의가 다소 난해하게 느껴질 수 있을 것 같아요! 일단, 정의를 외우려고 하지마시고 사례를 통해서 체감을 하시는게 좋아요!

• 사례 1

  function find_max_num(array) {
      for (let num of array) {
          let isMax = true;
          for (let compare_num of array) {
              if (num < compare_num) {
                  isMax = false;
                  break;
              }
          }
          if (isMax) {
              return num;
          }
      }
  }
  
  console.log("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]));
  console.log("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]));
  console.log("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]));
  

  • 이 함수의 시간 복잡도를 계산해볼까요?

  for (let num of array) { // array 의 길이만큼 아래 연산이 실행
  		let isMax = true;
  		for (let compare_num of array) { // array 의 길이만큼 아래 연산이 실행
  				if (num < compare_num) { // 비교 연산 1번 실행
  						isMax = false;
  						break;
          }
      }
  		if (isMax) { // 비교 연산 1번 실행하지만 미미하므로 편의상 실행시간엔 포함시키지 않을게요!
  				return num;
  		}
  }
  

  • 위에서 언급한 말을 다시 살펴볼게요.
    • 문제를 해결하는데 걸리는 시간과 입력의 함수 관계
  • 입력
    • array의 원소 갯수 = N
  • 실행 시간
    • array의 원소 갯수 X array의 원소 갯수만큼 비교 연산 = N X N
    • 그러면 우리는 이제 이 함수는 $N^2$ 만큼의 시간이 걸렸겠구나! 라고 말할 수 있습니다.
  • 시간 복잡도는 Big-O(빅오) 표기법으로 표시하며 이 경우엔 O($N^2$)의 시간 복잡도를 가진다고 합니다.

• 사례 2

  function find_max_num(array) {
      let max_num = array[0];
      for (let num of array) {
          if (num > max_num) {
              max_num = num;
          }
      }
      return max_num;
  }
  
  console.log("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]));
  console.log("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]));
  console.log("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]));
  

  • 이번에는 이 함수의 시간 복잡도를 계산해볼까요?

  let max_num = array[0]; // 연산 1번 실행
  for (let num of array) { // array 의 길이만큼 아래 연산이 실행
  		if (num > max_num) { // 비교 연산 1번 실행
  				max_num = num; // 대입 연산 1번 실행
  		}
  }
  

  • 입력
    • array의 원소 갯수 = N
  • 실행 시간
    • max_num 대입 연산 = 1번
    • max_num 대입 연산 1번 + array의 길이 X (비교 연산 1번 + 대입 연산 1번) = 1 + 2N
    • 마찬가지로 이 함수는 2N + 1의 시간이 걸렸겠구나! 라고 말할 수 있습니다.
    • 하지만, 빅오 표기법에서는 N의 지수부분만이 유효하게 쓰이고 나머지는 절삭합니다.
      • 다시 말해서 2N + 1 → O(N)입니다.

그러면 공간 복잡도는 뭔가요? (이 친구는 좀 심플하게!)

• 시간 복잡도와는 다르게 공간 복잡도는 문제를 해결하는데에 대한 공간과의 상관관계를 말합니다!