알고리즘26 시간 복잡도 이전에 알고리즘의 복잡도에 대해 잠깐 알아보았는데 그 복잡도 중 시간 복잡도에 대해 더 자세히 알아보려고 한다. 공간 복잡도의 경우 해당 알고리즘이 얼마나 많은 메모리 공간을 필요로 하는지 어느 정도 이해할 수 있는데 시간 복잡도의 경우 반복문이 얼마나 겹쳐 있는지, 또 어떻게 도출해 나가는지에 따라 시간 복잡도가 달라지기 때문에 직관적으로 바로 파악하기 힘든 경우가 많다. 또한 하드웨어 환경에 따라 처리시간이 달라지기도 하고, 소프트웨어 환경에 따라 처리시간이 달라지기도 한다. 이를 단순한 함수로 표현하기 위해서 점근적 표기(Asymptotic Notation)를 사용한다. 이는 입력 크기인 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법이다. 이러한 표기에는 크게 O(Big-O.. 2023. 3. 21. 복잡도 알고리즘은 쉽게 말해 어떠한 문제를 해결하기 위한 절차나 방법이라고 할 수 있다. 이런 알고리즘을 사용하는데에는 해당 알고리즘의 효율성을 따질 수 밖에 없다. 예를 들어 어떤 문제를 해결하는 데 있어서 어떤 알고리즘은 최적인 상황임에도 불구하고 100시간이 걸리고 또 어떤 알고리즘은 최악의 상황임에도 10시간이 걸린다면 당연히 후자의 알고리즘을 선택하는 것이 맞는 것이다. 반대로 전자의 알고리즘은 1kb의 메모리를 요구하고, 후자의 알고리즘은 100mb의 메모리를 요구한다면 메모리를 사용하는 데에 있어서는 전자의 알고리즘이 효율적인 것이다. 이를 따지기 위해서 사람들은 알고리즘의 효율성을 공간적, 그리고 시간적 효율성으로 나누어 판단했다. 우선 공간적 효율성은 연산량에 대비하여 얼마나 적은 메모리 공간을.. 2023. 3. 21. 이전 1 ··· 4 5 6 7 다음
