[data structure] - array

시간 복잡도(time complexity)
데이터 구조의 오퍼레이션 혹은 알고리즘이 얼마나 빠르고 느린지 측정하는 방법

실제 "시간 측정" x

-- > 1분,1초 단위의 시간계산 x
      얼마나 많은 단계가 있는가 o
=====>단계가 적은 것이 훌륭한 알고리즘

 

휘발성 메모리 vs 비휘발성 메모리

휘발성 메모리
Ram(Random access memory)
데이터 접속을 랜덤으로 하니까 빠르다
(메모리 박스를 가정했을때 1,2 순차적으로 메모리에 접속을 하는 것이 아니라서)

 

비휘발성 메모리
하드디스크

어레이
*최대 길이를 알려주어야 한다.*
그러면 컴퓨터 메모리가 길이만큼 메모리를 연속적으로 할당해준다.


Reading(배열을 어떻게 읽는가)
컴퓨터는 0 - based indexing
배열의 장점! 많은 자료를 읽어야 한다면 배열이 좋다.
배열이 컴퓨터가 어디서 시작하는지 알 수 있고 랜덤으로 액세스 가능하니까

searching
시간이 좀 걸린다.
액세스는 빠르지만 안의 뭐가 들어있는 지까지는 모르기 때문에 
하나하나 열고 맞는지 체크하는 과정 필요해(-> 이것을 선형 검색이라고 함 == > 처음부터 차례차례 찾는 것) 


inserting(adding)- 쓰기
만약 데이터를 추가할때 
뒤에 추가하는 경우는 쉽다- 어디서 시작하는지와 길이를 알고 있으니 뒤에 추가하기만 하면 돼
근데 앞의 추가하거나 중간에 추가하려면 배열안의 데이터를 옮겨주어야한다.
최악인 경우 배열이 꽉 찼는데 데이터를 넣어야할 경우 새로운 배열을 만들어주고
기존의 배열을 복사해서 넣어주어야하는데 배열의 크기가 크면 ..

deleting
배열에 추가하는것과 비슷
뒤에 삭제하는 것은 쉽다. 
중간에 삭제하면 공간이 생겨.. 그걸 메꾸기 위해 요소들을 앞으로 이동시켜 주어야해.
최악의 시나리오 배열의 첫번째 요소를 삭제-> 아이템이 많으면 ..