자료구조의 연산

읽기

• 자료구조내 특정위치를 찾아보는 것
• 컴퓨터는 딱 한 단계로 배열을 읽을 수 있으며, 프로그램에서 배열을 선언하면 연속된 빈 메모리 공간을 할당한다.
• 모든 메모리주소에 한번에 접근가능하며 배열을 할당할 때 어떤 메모리주소에서 시작하는지 기록해둔다.
• 배열은 기초적인 자료구조이지만 빠르게 읽을수 있는 강력한 자료구조이다.

 

검색

• 자료구조내 특정 값을 찾는 것
• 인덱스 제공 후 값을 반환하며 읽기에 비해 오래걸리며, 찾는 값이 가장 마지막 순서에 있다면 모든 값을 검색해야 한다.
• 배열에 값이 있다고 확신도 불가하다.
• N개로 이루어진 배열은 선형검색에 최대 N단계가 필요하다.

 

삽입

• 자료구조에 새로운 값을 추가하는 것
• 배열에 새 데이터를 삽입할 때 어디에 삽입하는가에 따라 효율성이 다르다.
• 배열에 맨끝에 삽입할때는 한 단계, 중간에 삽입할 경우 이동할 배열에 갯수 + 1단계, 최악의 시나리오는 처음에 삽입 N + 1단계가 소비된다.

 

삭제

• 자료구조에서 값을 제거하는 것
• 최악의 경우 N단계가 소요된다. 삭제 1단계 + 나머지 원소 이동 N-1 단계

 

속도측정

• 연산의 속도를 측정할 때 얼마나 많은 계산단계가 필요한가?
• 시간복잡도, 효율성, 성능, 속도등을 따져 보아야 한다.

 

집합

• 배열기반의 자료구조로 중복값의 삽입을 허용하지 않는다.
• 중복 데이터가 없을때 유용하며 배열과 달리 중복금지의 제약으로 인해 효율성이 크게 달라진다.
• 읽기 검색 삭제 연산은 똑같은 효율을 가지지만 삽입은 먼저 검색 한 후 삽입을 해야한다.
• 요구사항에 따라 배열보다 집합이 나은 경우가 있다.