빅오표기법 (Big-O notation), 보이는 학생

빅오표기법은 알고리즘의 시간 복잡도를 나타내는 표기법

아래와 예시와 같이 for문이 1번만 돌면 O(n) 

이중for문으로 쓰이면 O(n^2) 

 

시간 복잡도(알고리즘의 복잡도)를 비교하자면

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n)등의 순서로 복잡하다.

 

선생님에게 보이는 학생의 수를 구하는 알고리즘

for문을 중첩해서 구할 수 도 있겠으나 max라는 변수를 만들어서 한번만 루프를 돌리는게 더 낫다.

n과 관련된 그 어떤 변수를 루프 안에 쓰더라도, 루프가 하나라면 O(n)으로 나타내면 된다

    <script>
      function solution(arr) {
        let answer = 1,
          max = arr[0];
        for (let i = 1; i < arr.length; i++) {
          if (arr[i] > max) {
            answer++;
            max = arr[i];
          }
        }
        //for문을 이중포문하면 시간 복잡도가 O(n2)임, 포문 한번만 돌면 시간 복잡도가 O(n)
        return answer;
      }

      let arr = [130, 135, 148, 140, 145, 150, 150, 153];
      console.log(solution(arr));
    </script>

 

 

 

출처: https://holika.tistory.com/29 [Uing? Uing!!]