Array
Array(배열) 이란 연속된 메모리 공간에서 순차적으로 저장된 데이터의 모음입니다.
array는 동일타입의 데이터만 저장이 가능하며 'int'를 선언 했을때는 float,char 와 같은 다른 타입의 데이터를 저장할 수 없습니다.
기본적으로 파이썬에서는 Array를 제공하지 않기 때문에 array 모듈을 사용해서 array를 생성 할 수 있습니다.
array 모듈은 두가지 매개변수를 받으며 첫번째 매개변수는 type을 나타내는 typecode 이고 두번째는 대괄호로 묶인 요소 묶음입니다.
ex)
exam_arr = array('i',[1,3,2,4,5])
자세한 typecode 에 대한 설명은 파이썬 공식문서를 참고하면 좋다.
https://docs.python.org/ko/3/library/array.html
array — 효율적인 숫자 배열 — Python 3.10.6 문서
array — 효율적인 숫자 배열 이 모듈은 문자, 정수, 부동 소수점 숫자와 같은 기본적인 값의 배열을 간결하게 표현할 수 있는 객체 형을 정의합니다. 배열은 시퀀스 형이며 리스트와 매우 비슷하
docs.python.org
배열의 시간복잡도는 아래와 같다.
O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리한다
O(N) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가진다
Operation | Best case | Worst case |
접근(access) | O(1) | O(1) |
삭제(delete) | O(1) | O(N) |
삽입(insert) | O(1) | O(N) |
검색(search) | O(N) | O(N) |
접근(access)
하나의 인덱스에 해당하는 값을 찾아내는 방식이다.
바로 해당 인덱스 값을 찾아가는 단순 사칙연산이 수행되기 때문에 O(1) 의 결과가 나온다.
n번째 요소의 메모리 주소 = M + (n-1) * S
- 0이 아닌 사람기준 1번째 가정
삭제(delete)
삭제는 맨 끝의 값을 삭제할 경우 앞으로 당겨야 할 값들이 없기 때문에 O(1)의 시간 복잡도가 나올 수 있다.
하지만 값들의 사이 최악의 경우 맨앞의 값을 삭제할경우 많은 값들을 앞으로 당겨야 하기에 O(N) 의 시간복잡도가 나온다
삽입(insert)
삽입은 삭제와 마찬가지의 원리로 맨 끝에 삽입을 할경우는 뒤로 밀어낼 값이 없기 때문에 O(1)의 시간 복잡도가 나올 수 있다.
역시 삭제와 마찬가지로 최악의 경우 많은 값들을 뒤로 밀어야 하기때문에 O(N)의 시간복잡도를 가지게 된다
검색(search)
검색은 array에서 원하는 값을 찾는것이고 array에서는 liner search (선형탐색) 이라고 부른다
따라서 O(N)의 시간복잡도를 가지게 된다
결과적으로 Array는 삽입,삭제,검색에 있어서 O(N)의 시간복잡도를 가지고
접근할 때 있어서 O(1)의 시간복잡도를 가지기 때문에
삽입,삭제,검색을 많이하지않고 접근을 주로 하는 방식에서 사용하면 유리하다.
'Python > algorithm' 카테고리의 다른 글
그룹단어체커 [22.09.04] (0) | 2022.09.04 |
---|---|
커트라인 [22.09.04] (0) | 2022.09.04 |
[몸풀기] 자릿수 더하기(22.09.01) (0) | 2022.09.01 |
[몸풀기] 핸드폰 번호 가리기 22.08.31 (2) | 2022.08.31 |
[몸풀기] 짝수와 홀수 (22.08.29) (0) | 2022.08.29 |