복잡도

플랫폼: 프로그래머스
강의명: 어서와! 자료구조와 알고리즘은 처음이지?
강사명: 이시윤

---

1. 복잡도란?

문제를 해결하는 데, 자원을 요구하는 정도

---

2. 복잡도 종류

시간복잡도와 공간복잡도가 있다.

특히, 시간복잡도를 더 많이 고려한다.
시간복잡도는 다시 평균 시간복잡도와 최악 시간 복잡도로 나눈다.

---

3. 빅 오 표기법

---

4. 시간복잡도 종류

1. O(n)

2. O(logn)

작성한 알고리즘의 시간복잡도가 로그 시간이면 효율이 매우 좋은 알고리즘이다.

3. O($n^2$)

삽입정렬을 구현해보자.

"""
삽입정렬의 시간복잡도: O(n^2)
"""
import unittest
from typing import List


def insertion_sorting(L: List) -> List:
    length = len(L)
    if length <= 1:
        return L
    for i in range(length):
        for j in range(i + 1):
            if i == j:
                break
            elif L[j] > L[i]:
                L[i], L[j] = L[j], L[i]
    return L


class 삽입정렬_테스트(unittest.TestCase):
    def test_빈_리스트는_빈_리스트를_리턴한다(self):
        L = []

        res = insertion_sorting(L)

        self.assertEqual(L, res)

    def test_원소가_한_개인_리스트는_그대로_리턴된다(self):
        L = [100]

        res = insertion_sorting(L)

        self.assertEqual(L, res)

    def test_음수가_포함된_정렬된_리스트도_정렬된다(self):
        L = [-10, 5, 15]

        res = insertion_sorting(L)

        self.assertEqual(res, sorted(L))

    def test_음수가_포함된_정렬되지_않은_리스트도_정렬된다(self):
        L = [5, 0, -15, -10]

        res = insertion_sorting(L)

        self.assertEqual(res, sorted(L))

    def test_음수로_이뤄진_리스트도_정렬된다(self):
        L = [-99, -3443, -33, -1213]

        res = insertion_sorting(L)

        self.assertEqual(res, sorted(L))

    def test_음수와_영_그리고_양수로_이뤄진_리스트도_정렬된다(self):
        L = [-99, -3443, -33, -1213, 324, 33, 111, 333, 333, 0, 777]

        res = insertion_sorting(L)

        self.assertEqual(res, sorted(L))

    def test_동일한_수로_구성된_리스트도_정렬된다(self):
        L = [1 for _ in range(9)]

        res = insertion_sorting(L)

        self.assertEqual(res, sorted(L))


if __name__ == "__main__":
    unittest.main()

4. O(nlogn)

5. O($2^n$)

---

5. 객관식 문제 풀이