목록2022/09/01 (1)

넘치게 채우기

[자료구조] 0. 시간 복잡도와 공간 복잡도, 빅-오 표기법 (Time Complexity, Space Complexity, Big - O notation)

좋은 알고리즘이란 무엇일까? 실행 속도가 빠르고, 컴퓨터의 메모리를 적게 사용하는 것이 좋은 알고리즘이 될 것이다. 알고리즘이 얼마나 빠른지와, 얼마나 메모리를 적게 쓰는지를 평가할 때는 알고리즘의 시간 복잡도(Time Complexity), 공간 복잡도(Space Complexity)라는 척도를 이용한다. 시간 복잡도 시간 복잡도는 알고리즘의 속도에 대한 척도이다. 시간복잡도를 측정하는데는 연산이 이뤄지는 횟수를 센다. 연산은 데이터 입출력, 산술, 반복문, 조건문과 같은 제어문이 있다. 입력 데이터의 수 n에 따른 연산횟수의 함수 T(n)을 구성하고, 데이터의 수 n의 변화와 그 연산횟수 T(n)의 변화를 분석하여 알고리즘의 시간 복잡도를 평가한다. 선형 탐색(순차 탐색) 알고리즘을 예로 들어보면: ..
컴퓨터과학/자료구조 2022. 9. 1. 23:22
이전 Prev 1 Next 다음