배열(array)
출처 : https://www.youtube.com/watch?v=NFETSCJON2M&list=PL7jH19IHhOLMdHvl3KBfFI70r9P0lkJwL&index=3
1. 시간복잡도란?
데이터 구조의 오퍼레이션 혹은 알고리즘이 얼마나 느리고 빠른지 측정하는 것
실제 시간을 측정하는 것이 아니라 얼마나많은 단계[steps]가 있는가로 측정단계가 적을수록 좋은 것
5 step > 20 step
2. 메모리 관점에서 배열이 어떻게 보일까?
✨ 메모리의 종류
volatile(휘발성) 메모리 : RAM, 컴퓨터를 껐다 키면 데이터가 사라짐
프로그램이 돌아가고,
변수를 생성할 때, RAM에 저장RAM(Random Access Memory) : 하드 드라이브보다 데이터 읽는 것이 빠르며, 데이터 접속을 랜덤으로 가능
004
005
006
007
008
009
010
011
012
위와 같이 RAM이
데이터를 넣은 박스라고 생각해보면 프로그램이 RAM에게 006으로 가주세요 하면 랜덤하게 접속 가능하기에 데이터를 읽는 것이 빠른 것, 바로 이동 가능(순차적으로 가는 것이 아니기 때문)
non-volatile(비휘발성) 메모리
하드 드라이브 같은 것, 컴퓨터를 껐다 키면 데이터가 사라지지 않음
즉, 메모리 관점에서 배열을 만들때, 컴퓨터에게 이게 얼마나 긴지 설명해야 함
나의 배열은 4개 만큼 길어 미리 예약/할당해줘! 메모리 안에서 박스들이 나란히 위치할 수 있게
배열은 검색, 추가,삭제시 느려짐
3. 배열
✨ Reading : O(1)
메모리 주소 001 002 003 004
index 0 1 2 3
위치만 알면, 배열의 데이터에 접속 가능
⇒ 배열에서 읽어내는 것이 빠름, 컴퓨터는 배열이 어디서 시작되는 지 아니까
EX. 피자를 원하면 컴퓨터에게 인덱스 1번의 값을 달라고 하면 됨
많은 자료를 읽어내려면 배열이 Good, 배열의 요소의 개수 상관없이
Random하게 읽어내니까배열에서 요소에 접근하거나 값을 변경하는 작업은 항상 입력 크기의 관계 없이 일정한 시간 내에 실행
예를 들어, 배열의 첫 번째 요소에 접근하거나 값을 변경하는 작업은 항상 고정된 시간만큼 걸린다.
이는 입력 크기에 관계없이 동일하게 빠르게 실행되며, 이러한 특성 때문에 배열의 Big O 표기법은 **
O(1)**로 표현
✨ Searching : O(n)
해당 값(=ex. 피자)가 배열에 있는지, 없는지 모름
어디에 있는지도 모르기 때문에 검색
하나하나 다 뒤져봐야 함
So, 읽는 것보다 시간이 많이 걸림
Random Access가 있어 주소를 찾아 박스에 쉽게 접근은 가능하나, 그 박스를 열어야 값을 확인 가능배열의 아이템을 하나하나 열어보고 맞는지 체크하는 과정을 하나하나 해야함
Linear Search[선형 검색] : 순서대로 0부터 끝까지 차근차근 찾는 것
✨ Insert[Add] 혹은 배열에 쓰기 : O(n)
만약, “tomato”를 넣고 싶다면, 미리 공간을 확보해뒀으니까 공간 걱정은 No!
결국
어디에토마토를 추가할 것인가!만약 중간이 앞에
추가하고 싶다면 나머지 값들을 옮겨야 함(아래와 같이)근데 만약.. 공간이 꽉 차 있는데 값을 추가하면 배열의 길이는 정해져 있기 때문에 곤란
⇒ 해결방안 : 새로운 배열을 만들고, 그 배열에 이전 배열을
복사하고, 새로추가해야 함그래서 시간이 오래걸리고 복잡
✨ Delete : O(N)
배열에 뭔가를 추가하는 것과 비슷
배열을 이리저리 움직여야 함
EX. “ice cream”을 없애고 싶어 ⇒ 삭제 후 공간을 채우기 위해 앞으로 땡겨야 함
4. 결론
배열의 통합적인 빅오는 배열의 각 연산의 최악의 경우(
O(N))를 종합한 결과일 수 있다.배열은 접근 연산을 제외하면 탐색, 삽입, 삭제 연산에 대해 비교적 효율적이지 않은 편이므로, 알고리즘을 설계할 때 이러한 연산의 효율성을 고려
오히려 데이터 추가 및 삭제는 연결 리스트가 더 빠르고 배열은 느림 배열은 모든 상자를 앞으로 옯겨야 추가가 가능하지만, 연결 리스트는 선을 바꿔서 연결해주기만 하면 되기 때문
Last updated