유혹하는 개발하기

알고리즘의 시간을 표현할 때 ‘빅 오 표기법’을 쓴다. 알고리즘 실행에 필요한 단계를 나타내기 위해 컴퓨터 공학자들이 수학에 쓰이는 용어를 가져온 것이다. 수학에서의 ‘빅 오’란? 빅 오는 수학에서는 함수의 성질을 나타낼 때 쓰이는 말이다. 함수 증가율의 상한값으로 설명되기도 한다. 또는 함수 g(x)가 f(x)의 속도보다 빠를 수 없을 때, g는 O(f)에 속한다고...

저번 포스팅에서는 자료 구조의 특징에 따라 연산 속도가 어떻게 변화하는지 보았다. 집합의 ‘중복을 허용하지 않는다’는 특징때문에 삽입 연산에서 배열에 비해 N단계가 추가된 2N+1 단계가 필요했다. 이번에는 검색 알고리즘을 예시로, 알고리즘에 따라 연산 속도가 어떻게 변하는지 본다. 정렬된 배열 정렬된 배열은 순서가 있는, 순서대로 요소가 나열된 배열이다. 정렬 배열은 특정한 검색...

자료구조와 알고리즘을 왜 배우는 걸까? 결론부터 말하면, 같은 연산이라도 자료 구조와 알고리즘에 따라 연산의 단계가 달라지기 때문이다. 알고리즘이 실행 속도에 영향을 준다는 것은 상식적으로 이해 가능하니, 아래 예시에서 자료 구조가 실행 속도에 어떻게 영향을 줄 수 있는지 알아보자. 배열의 연산 : 읽기, 검색, 삽입, 삭제 읽기 인덱스와 메모리 주소를 통해...

시간복잡도(Time Complexity)의 개념 알고리즘을 처리하는데 걸리는 시간 ​ 연산을 실행 시간으로 측정하기 어려운 이유 검색이라는 연산을 할 때 최초의 CPU 4004를 탑재한 컴퓨터와 최신 CPU를 탑재한 컴퓨터는 속도에서 큰 차이를 보일 것이다. 같은 CPU라도 작업 프로세서를 많이 띄워놓고 있다면 프로그램 실행이 느려질 수 있다. 이렇게 프로그램 연산 속도를 시간으로 따지는...