Joslynn의 하루

빅 오 표기법 : 알고리즘의 효율성을 표시하는 표기법 : 빅 오 표기법을 사용하면 어떤 알고리즘을 다른 알고리즘과 비교해서 표현하는 것이 가능하다. : 위 그래프는 복잡도가 n인 알고리즘에 빅 오 표기법을 적용한 결과이다. : x축은 복잡도 n, y축은 필요한 일의 양이나 메모리를 의미 : 다른 알고리즘이 이 그래프의 어떤 위치에 있는지에 따라 복잡도 n인 알고리즘과 다른 알고리즘의 복잡도를 비교할 수 있다. : 다른 알고리즘이 복잡도 n인 알고리즘의 아래에 있다면, 같은 일을 하는 데 시간이 덜 들기 때문에 더 빠른 알고리즘 : 반대로, 복잡도 n인 알고리즘의 위에 있다면, 더 느린 알고리즘 알고리즘 간 관계 표현 - O (빅 오) : 비교 대상인 그래프가 일치 혹은 아래에 있을 때. 비교 대상인 다른..

시간 복잡도 시간 복잡도는 서로 다른 알고리즘의 효율성을 비교할 때 사용 - Rule 1: input \geq≥ 0 - Rule 2: functions do more work for more input - Rule 3: drop all constants - Rule 4: ignore lower order terms - Rule 5: ignore the base of logs - 2n = O(n)2n=O(n) => 2n \in O(n)2n∈O(n) 규칙 1. 입력값(n)은 항상 0보다 크다. : 입력값이 음수일 수는 없다. : 복잡도는 항상 0보다 크다고 가정하고 계산 규칙 2. 함수는 많은 입력값이 있을 때 더 많은 작업을 하게 된다. : 더 많은 입력값이 주어지면 어떤 작업을 하는 데 필요한 계산이나 ..