시간복잡도란?
데이터 구조의 오퍼레이션 혹은 알고리즘이 얼마나 빠르고, 느린지 측정하는 방법이야.
시간을 측정하는 것이 아니라 얼마나 많은 단계가 있는가로 측정한다.
그래서 단계가 적을수록 좋은것이다.
예시로 만약 어떤 오퍼레이션이 5개 단계(step)만 요구 된다면 ,
같은 작업을 하는데 20단계를 요구하는 알고리즘 보다 훌륭한 알고리즘 이다.
메모리(휘발성 메모리 , 비휘발성 메모리)
volatile 휘발성 메모리(램 메모리)
컴퓨터를 끄게 되면 저장되어 있던 데이터가 사라진다.
- RAM 에서 데이터를 읽는것이 하드 드라이브에서 읽는것보다 속도가 빠르다.
(왜냐하면 이름이 적혀 있는것처럼 데이터 접속을 랜덤으로 할수 있기 때문이다.)
non-volatile 비휘발성 메모리(하드 드라이브)
컴퓨터를 껐다가 다시 켜도 하드 드라이브의 데이터가 그대로 인것을 비휘발성 메모리 라고한다.
Array
reading
배열에서 읽어내는건 빠르다.
컴퓨터는 배열이 어디서 시작하는지를 알고 있기 때문이다.
그래서 많은 자료를 읽어야 한다면 배열이 짱이다.
왜냐하면 Random Access 덕분이다.
배열이 얼마나 긴지와 관계없이 인덱스에서 요소를 읽어내는 속도는 동일하기 때문이다.
배열에 요소가 5개든. 100개가 있든. step 은 동일하다.
searching
검색은 조금 오래 걸린다.
왜냐하면 검색할땐 찾는값이 배열에 있는지 없는지 , 어디에 있는지 조차 모르기때문에 하나하나 다 뒤져봐야 하기 때문이다.
그래서 Random Access 가 있어서 박스를 쉽게 접근할수 있지만
그 박스안의 값은 모르는 그런 상황 인것이다.
예시)
내가 원하는 값을 찾으려면 배열의 아이템을 하나하나 열어보고 맞는지 체크하는 그 과정을 하나하나 해야한다.
만약 찾는 아이템이 인덱스 첫번째에 있다면 금방 찾고 끝나겠지만 중간이나 끝에 있는 경우라면 처음부터 끝까지 하나하나 열어보고 체크해야할 것이다.
만약 찾는값이 없는경우는 처음부터 끝까지 찾아야하니까 정말 시간이 오래걸릴것이다.
이렇게 순서대로 0부터 끝까지 차근차근 찾는것을 Linear Search(선형검색) 이라고 한다.
insert 혹은 배열에 쓰기
배열을 만들 때에는 메모리 공간을 미리 확보해야한다.(5개의 item 길이라고 이야기해줘야 한다.)
- 배열의 맨 뒤에 아이템이 들어가는 경우에는 괜찮지만 중간이나 맨 앞으로 아이템이 들어가야 하는 경우는 배열에 들어가 있는 아이템을들 하나하나 뒤로 옮기는 과정을 실행해야하기 때문에 오래 걸린다.
- 기존 배열은 5개의 메모리 공간을 할당해 놨는데 이미 5개가 꽉차고 더이상 데이터가 들어갈 곳이 없는경우 , 더 큰 새로운 배열을 만들어 기존 데이터를 복사하여 넣은 후 추가로 들어갈 데이터를 삽입 해야하기 때문에 또 오래 걸린다.
delete
삭제는 배열에 뭔가를 추가하는것과 비슷하다.
1. 배열의 마지막 아이템을 삭제하는 것은 쉽다.
(왜냐하면 컴퓨터는 배열이 어디서 시작하고, 얼마나 긴지 기억하기 때문이다)
2.배열의 중간요소를 삭제해야하는 경우는 배열 중간에 공백이 있으면 안되기 때문에 모든 배열의 값들이 움직여야 한다.
3. 배열의 첫번째 요소를 삭제해야하는 경우 모든 배열의 값들이 움직여야한다.
이렇게 배열에서 오락가락 움직이는것이 4~5개 적은 갯수라면 상관이 없지만 몇천개의 아이템이 있는 상황이라면 아주 오래.. 시간이 걸릴것이다.
정리를 하면
1. 배열은 데이터를 읽을땐 정말 빠르다.
2. 하지만 검색, 추가 , 삭제 를 해야하는 경우에는 느려진다.
(추가 , 삭제를 해야하는 경우라면 배열의 맨 끝에서 작업하는것을 추천한다.)
