배열(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) : 하드 드라이브보다 데이터 읽는 것이 빠르며, 데이터 접속을 랜덤으로 가능
| 001 | 002 | 003 |
|---|---|---|
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