[6강] 알고리즘의 복잡도(Comlexity of Algorithms)

황인용·2020년 7월 8일
1
post-thumbnail

시간 복잡도(Time Complextiy)

  • 문제의 크기와 이를 해결하는데 걸리는 시간 사이의 관계

공간 복잡도(Space Complexity)

  • 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계

평균 시간 복잡도(Average Time Complexity)

  • 임의의 입력 패턴을 가정 했을 때 소요되는 시간의 평군

최악 시간 복잡도(Worst-case Time Complexity)

  • 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

Big-O Notation

  • 점근 표기법(asymptotic notation)의 하나
  • 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현
    (알고리즘의 복잡도를 표현할 때 흔히 쓰임)
  • O(log n), O(n), O(n2), O(2n) 등으로 표기

O(n) - 선형 시간 알고리즘

  • 입력의 크기에 비례하는 시간 소요

  • Average case : O(n)

  • Worst case : O(n)

O(log n) - 로그 시간 알고리즘

  • 입력의 크기의 로그에 비례하는 시간 소요

O(n2) - 이차 시간 알고리즘

  • Best case : O(n)

    • 정렬되어 있는 리스트라면 Best case
  • Worst case : O(n2)

  • divid(나누기)

  • conquer(합치기)

  • O(n * logn)

복잡한 문제


[퀴즈] 알고리즘의 복잡도 객관식문제

정답 3. O(NlogN)

정답 1. O(logN)

정답 2. O(N)

정답 4. O(N2)

정답
오답 : 4. O(N2)
정답 : 5. O(N3)

참고

profile
dev_pang의 pang.log

0개의 댓글