오늘의 학습 주제
알고리즘
새로 알게된 내용
알고리즘의 개념 - 문제를 해결하기위한 절차, 방법을 자세히 순서대로 규칙을 명확하게 나열하는것이다.
알고리즘의 중요성 - 효율적인 알고리즘은 컴퓨터 프로그래밍에서 컴퓨터의 자원(메모리, 시간)등에 직접적으로 영향이 갈 수 있으며, 효율적으로 사용하는것이 중요하다.
Big O 표기법
알고리즘의 효율성을 나타내는 표기법으로 알고리즘이 얼마나 많은 시간과 공간을 필요로 하는지 알 수 있고, 해당 알고리즘의 최악의 성능을 알 수 있다.
표기법)
O(1) : 상수 시간으로 입력의 크기에 상관없이 항상 일정한 시간이걸립니다.
O(n) : 선형 시간으로 입력의 크기에 비례하여 시간이 걸립니다.
O(n^2): 이차 시간. 입력의 크기의 제곱에 비례하여 시간이 걸립니다.
O(log n): 로그 시간. 입력의 크기의 로그에 비례하여 시간이 걸립니다.
Big O표기법 계산
상수 항목이나 낮은 차수의 항목은 버린다.
O(2n),O(3n^2)의 경우 이렇게 간소화할 수 있다.O(n),O(n^2)
가장큰 차수의 항목만 남기고 버린다.
O(n^2 + n)의 경우 이렇게 간소화할 수 있다.O(n^2)
다항식은 낮은차수의 항목을 버린다.
O(3n^3 + 5n^2 + 2n + 7)의 경우 이렇게 간소화할 수 있다.O(n^3)
연산자나 상수 값을 버린다.
O(3n^2 + 4n + 2)의 경우 이렇게 간소화할 수 있다.O(n^2)
시간복잡도
알고리즘이 문제를 해결하는데 걸리는 시간으로, 입력 크기에 대한 연산횟수로 측정합니다.
공간복잡도
입력 크기에 따라 필요한 저장공간의 양을 측정한다.
