자료구조

시간복잡도(Time Complexity)

실행 시간은 input size에 따라 변한다. 보통 최악의 경우를 생각해서 알고리즘을 고른다. 시간 복잡도 n만큼의 인풋이 들어왔을때의 number of operations을 표현하는 방식. (실제 실행시간이 아님) 공간 복잡도 알고리즘이 요구하는 메모리의 양을 표현. ex) Scalar:O(1) Vector:O(n) Matrix:O(n^2) 주로 다룰것은 시간 복잡도!(Time Complexity) 시간 복잡도는 알고리즘의 정확한 연산 횟수를 나타내기 위해서 사용하는 것이 아님. n이 커질때 연산횟수가 얼마나 늘어나느냐 하는 그 추이를 표현하고, 그것을 통해 어느 알고리즘이 더욱 효율적인지를 판단하기 위해 사용하는 것이다. 그렇기 때문에 상수나 최고차항이 아닌 n값등은 무시를 하게 된다.(n이 매우 ..