파이썬 데이터구조(자료구조) (4) 썸네일형 리스트형 배열과 리스트, Stack 과 Queue 배열의 시작 주소, 저장된 값의 종류(바이트 개수), 몇 번째에 저장되어 있는지를 나타내는 인덱스 (index) 세 가지 정보만으로 값이 저장된 곳의 주소를 계산할 수 있다 인덱스로 배열의 특정 위치에 있는 값을 O(1)시간(상수 시간) 내에 읽고 쓸 수 있는 두 개의 기본연산을 제공하는 자료구조를 배열이라고 한다. -C의 배열은 읽기/쓰기 연산만 제공하는 제한된 자료구조 Python -C 언어 배열의 셀에는 실제 값(데이터)이 저장된 형식이지만, Python 리스트의 셀에는 데이터가 아닌 데이터가 저장된 곳의 주소(address 또는 reference)가 저장된다 항상 객체의 주소만 저장하기 때문에, 리스트의 셀의 크기를 메모리의 주소를 표현할 수 있는 (4 바이트 또는) 8 바이트로 고정하면 된다. .. Big-O 표기법 Big-O 표기법 1. 최악의 입력에 대한 기본연산의 횟수를 정확히 세는 건 일반적으로 귀찮고 까다롭다. 2. 정확한 횟수보다는 입력의 크기 n이 커질 때, 수행시간의 증가하는 정도가 훨씬 중요하다. 3. 수행시간 함수 T(n)이 n에 관한 여러 항(term)의 합으로 표현된다면, 함수 값의 증가율이 가장 큰 항 하나로 간략히 표기하는 게 시간 분석을 간단하게 하는 데 큰 도움이 된다. 4. 예를 들어, T(n) = 2n + 5이면, 상수항보다는 n의 일차항이 T(n)의 값을 결정하게 되므로 상수항을 생략해도 큰 문제가 없다 파이썬 데이터구조(자료구조)-알고리즘 시간복잡도(2) 2023.01.13 - [파이썬 데이터구조(자료구조)] - 파이썬 데이터구조(자료구조)-알고리즘 시간복잡도(1) 파이썬 데이터구조(자료구조)-알고리즘 시간복잡도(1) 알고리즘 성능 즉 수행시간(시간복잡도)를 어떻게 측정할까? 결론부터 말하자면 가상 언어로 작성된 가상코드를 가상컴퓨터(virtual machine)에서 시뮬레이션 함으로써 측정한다. Why? --> 실제 코드(C itpoopl.tistory.com 해당 글을 먼저 읽고 오셔야 이해하실 수 있습니다. 지난 시간에 알고리즘 수행시간=최악의 입력(worstcase input)에 대한 기본연산 횟수 라는 사실을 알아보았다. ``` algorithm arrayMax(A, n) input: n개의 정수를 저장한 배열 A output: A의 수 중에서 .. 파이썬 데이터구조(자료구조)-알고리즘 시간복잡도(1) 알고리즘 성능 즉 수행시간(시간복잡도)를 어떻게 측정할까? 결론부터 말하자면 가상 언어로 작성된 가상코드를 가상컴퓨터(virtual machine)에서 시뮬레이션 함으로써 측정한다. Why? --> 실제 코드(C, Java, Python 등)로 구현하여 실제 컴퓨터에서 실행한 후, 수행시간을 측정할 수도 있지만, 각 개개인의 HW/SW 환경에 따라 같은 알고리즘이라도 다른 수행시간이 발생 할 수 있기 때문이다. Ram 현재 가장 많이 사용하는 가상컴퓨터 모델은 (real) RAM(Random Access Machine) 모델이다. RAM 모델은 CPU + memory + primitive operation으로 정의된다. -연산(operation, command)을 수행하는 CPU -임의의 크기의 실수도 .. 이전 1 다음