본문 바로가기

자료구조8

자료구조 - 시간복잡도 , Big-O(2022.09.18) 1. 시간복잡도 알고리즘의 수행시간은 최악의 입력에 대한 기본 연산 횟수로 정의한다. 사실 모든 입력에 대해 기본연산 횟수를 더한 후 평균을 낸 값이 정확한 값이지만 이는 현실적으로 불가능하므로 가장 안 좋은 입력에 대한 기본 연산 횟수를 측정하여 정의한다. 시간복잡도에 대한 예제로 아래 상황을 생각해보자. 1) 최댓값 구하기 algorithm arrayMax(A,n) currentMax = A[0] for i = 1 to n-1 do if CurrentMax < A[i] currentMax = A[i] return currentMax arrayMax의 W.C.I (Worst Case Input)은 어떤 걸까? 가장 최악의 상황은 for구문의 모든 값에 대해 if 구문이 참이어서 currnetMax의 값.. 2022. 9. 19.
자료구조 - 자료구조와 알고리즘(2022.09.13) 1. 자료구조 1) 자료구조란? data가 있을 때, 이를 저장할 저장공간과 읽기, 쓰기, 삽입, 삭제, 탐색 등 data를 다룰 수 있는 연산이 필요하다. 이 저장공간과 연산을 통틀어 우리는 자료구조라고 부른다. 2) 자료구조의 예 ▶변수(variable) a = 1 print(a) 위 코드에서 첫째줄에는 a에 5가 들어있는 객체의 주소를 입력하는 쓰기 연산이 사용되었으며, print(a)에는 a에 쓰인 data를 읽는 읽기 연산이 사용되었다. 이처럼 변수도 자료구조의 간단한 예 중 하나이다. ▶배열(array) / 리스트(list) A[9,1,-7,2] 위와 같은 배열에서 각 배열의 자리에 각 숫자가 들어있는 주소가 입력되는 쓰기 연산이 사용되었고 이를 출력한다면 읽기 연산이 사용되게 된다. 뿐만 아.. 2022. 9. 13.