🟦 자료구조의 연산과 연산의 속도 측정
🔷 자료구조 연산
자료구조의 '읽기', '검색', '삽입', '삭제'를 '연산'이라고 한다.
자료구조의 성능을 알려면 코드가 자료 구조와 일반적으로 어떻게 상호작용하는 지 알아야 한다. 자료구조는 '읽기', '검색', '삽입', '삭제' 네 가지 기본 방법을 사용하여 코드와 상호작용을 하며 이것을 '연산'이라고 한다.
✅ 읽기
읽기는 자료구조 내 특정 위치를 찾아보는 것이다.
✅ 검색
검색은 자료구조 내에서 특정 값을 찾는 것이다.
✅ 삽입
삽입은 자료구조에 새로운 값을 추가하는 것이다.
✅ 삭제
삭제는 자료구조에서 값을 제거하는 것이다.
🔷 연산의 속도 측정
연산의 속도는 얼마나 많은 계산단계(step)가 필요한지를 따지는 것이다. 단계 수 측정이 연산속도를 분석하는 핵심비결이다.
'시간복잡도' = '속도' = '효율성' = '성능' = '주어진 연산에 걸리는 단계 수'
연산이 얼마나 "빠른가"를 측정할 때는 시간 관점이 아니라 몇 단계가 필요한지를 고려합니다. 시간은 실행하는 하드웨어에 따라 항상 바뀌므로 시간을 기준으로 속도를 측정하면 신뢰할 수가 없기 때문입니다. 예를 들면 어떤 컴퓨터는 5초가 걸리고, 구형 컴퓨터라면 더 오래 걸릴 것이고, 미래의 슈퍼컴퓨터에서는 1초도 안 걸릴 수도 있습니다.
그래서 연산의 속도를 측정할 때 얼마나 많은 계산단계(step)가 필요한가를 따져봅니다. 예를 들어 연산 A에는 5단계가 필요하고 연산 B에는 500단계가 필요하다면, 모든 하드웨어에서는 연산 A가 연산 B보다 항상 빠를 거라고 가정할 수 있기 때문입니다.
🟦 출처
🔷 글의 내용
이 글 내용은 '제인 웬그로우'의 '누구나 자료구조와 알고리즘 개정 2판' 책을 100% 참고하여 작성하였습니다. 설명에 전문적인 용어보다는 일상적인 용어를 사용하고 그림으로 원리를 설명해주어 왕초보인 저가 이해하기에 아주 좋았습니다. 가격이 많이 나가는 편이지만 꼭 배워야 하는 내용이 모두 들어있고 그것을 제가 이해할 수 있는 수준으로 쓰여있어 전혀 아깝지 않은 소비였습니다.
