시간복잡도

    [알고리즘] 시간복잡도(Time Complexity)

    이전 포스팅에서 알고리즘에 대한 개념을 설명했다. 그 중, 시간복잡도라는 개념이 나왔는데 밑의 그림을 예로 들었는데 이해가 쉬우리라 판단된다. 보이는 것처럼, "알고리즘"이 수행되는 시간이 시간복잡도이다. 비슷한 친구로 "공간복잡도" 라는 개념도 있는데, 반대로 "메모리"를 얼마나 사용하는지에 대한 용량의 개념이다. 데이터를 저장할 수 있는 메모리와 저장매체의 발전으로 인하여 메모리에 대한 개념 또한 그렇게 큰 범주가 되지 못하고 있다. 예컨데, 예전 프로그래밍에서 배열이나 동적할당을 최소화 하고 컴파일을 최소화하며.. 등등 메모리가 얼마 없던 시절의 최적화 하기 위한 행동들은 지금은 하지 않아도 된다. 다만, 최적화의 범주에서 볼 때 좋은 행동이라고 볼 수 있다. 시간복잡도의 그래프가 또 빠질 수 없는..

    [알고리즘] 알고리즘 종류 및 시간복잡도 정리

    알고리즘(Algorithm) 이란? "문제를 해결하는 방법" 이다. 특히, 컴퓨터에서 알고리즘이란 거의 안 쓰이는 곳이 없을 정도로 널리 이용되고 있다. 어떠한 Input 데이터가 주어지면 이것을 사용하기 편하게 문제를 해결한 형태의 Output을 만든다. 여기서 계속 문제를 해결한다고 하는데, 컴퓨터에서 알고리즘을 사용하는 이유는 대개 다음과 같은 이유로 사용하게 된다. 자료구조 - 정렬, 탐색, 트리, 힙트리구조 - DFS, BFS그래프 - 최단거리정수론, 난수발생, 해석기하, 그래픽 등.대부분의 경우 "자료구조"와 관련된 알고리즘이 직접적으로 사용할 일이 많아서 주로 쓰게 된다. 간단하게 하나 하나 정리해보면 1. 자료구조(Data Structure) "정렬"에 관련된 알고리즘이 가득하다. 데이터를..