목록파이썬 알고리즘 (26)

반원 블로그

03d. 시간 복잡도 계산과 빅오(Big-Oh) 표기법

알고리즘 분석에 인정되는 연산 연산 횟수에 카운트 되는 기본 연산은 다음과 같습니다. 변수에 값을 배정 함수를 호출 산술연산(더하기, 빼기, 곱하기, 나누기 등) 비교연산(크다, 작다, 같다, 아니다) 인덱싱을 이용한 코드 반환(return) 참조 또는 내부 속성 접근 시간 복잡도 T(n) 계산 만일 n개의 데이터서 각각 기본연산 3번씩한다면 시간 복잡도는 다음과 같습니다. T(n) = n * 3 = 3n 빅오(Big-Oh) 표기법 경우에 따라서 정확한 시간복잡도를 구하는 게 어려울 수 있습니다. 이에 가장 차수가 높은 것만 남겨놓아 비교하는 빅오 표기법이 있습니다. 차수가 높은 n이 처리할 데이터가 많을수록 그 차이가 크기 때문입니다. $T(n) = n^5+n^3+n+5$ => $O(n) = n^5 $..
2018~/파이썬 자료구조 알고리즘 2019. 5. 10. 00:13
03c. 속도 기준 알고리즘 비교

속도로 분석하는 과정 생각보다 단순합니다. 연산 횟수를 셉니다. 1과 처리해야 되는 데이터 수에 대한 관계를 분석합니다. 2를 통해 관계식(또는 함수) T(n)을 세웁니다. 최악의 상황을 분석하자. 복잡한 동전 지갑에서 눈을 가리고 500원을 찾는다고 가정하자. 이 때의 최선, 평균, 최악의 경우를 적어보면 다음과 같습니다. 최선 : 첫 동전부터 500원! 평균 : 반절정도 꺼냈을 때 500원을 발견! 최악 : 처음부터 500원은 있지 않았다... 최선의 경우를 분석해봤자 별 의미는 없겠죠. 단순히 "운이 좋았다"로 정리할 수도 있습니다. 결론적으로 말해서 알고리즘을 분석할 때 최악의 경우(Worst Case)으로 상황을 둡니다. 알고리즘 이용자 입장에서는 발생 빈도가 높은 평균의 경우(Average C..
2018~/파이썬 자료구조 알고리즘 2019. 5. 9. 00:15
03b. 성능 분석의 기준

양질의 자료구조와 알고리즘을 구분하는 기준 시간은 귀중합니다. 그렇기에 양질을 판단하는 대표적 척도는 실행시간(Running time) 입니다. 자료구조의 연산, 알고리즘이 수행하는 절차에서 효율성에 관심을 가져야합니다. 또한 메모리 사용 크기(공간)도 고려해야합니다. 단순히 용량 뿐만 아니라 실행시간에 영향을 주기 때문이죠.(쓸 데 없이 짐이 크면 나르기 힘들잖아요.) 추가로 처리해야되는 데이터의 개수와 크기에 따라 어떻게 실행시간이 바뀌는 지에 대한 관계도를 고려해야합니다. 경우에 따라 격차가 작을수도, 엄청 클 수도 있기 때문인데, 이에 대해서 빅오(Big-Oh) 표기법에서 알아봅시다. 시간 복잡도와 공간 복잡도 최적의 알고리즘은 시간 복잡도와 공간 복잡도로 분석한 결과가 좋음을 뜻합니다. 시간 복..
2018~/파이썬 자료구조 알고리즘 2019. 5. 8. 00:16
03. 성능분석 기법

자료구조와 알고리즘의 성능을 분석하는 기법과 도구에 대해 알아봅니다. 위키독스 연재 : https://wikidocs.net/book/2868
2018~/파이썬 자료구조 알고리즘 2019. 5. 7. 00:23
03a.자료구조와 알고리즘

자료구조와 알고리즘의 관계 자료구조는 자료를 구성하고 접근하는 체계적인 방법에 대한 것이라면, 알고리즘은 어떤 일을 수행하는 일련의 과정이자 단계적인 절차라 할 수 있습니다. 우리는 의도하지 않았지만 앞서 '단일 연결 리스트'와 '이중 연결 리스트'를 구현하며 삽입, 출력, 삭제, 탐색 연산을 설계했습니다. 각 연산은 우리가 설계한 단계에 맞춰 기능을 수행하므로 알고리즘이라 볼 수 있습니다. 사실상 자료구조와 알고리즘을 둘 다 만든 것이죠. 그러나 우리가 결과적으로 알고리즘을 만들었으나, 전문서적 및 분야에서 말하는 알고리즘과는 조금 차이가 있습니다. 전자는 '단계적인 절차'인 사전적 의미를 가지며, 후자는 '효율적이고 양질의 성능을 가진 단계적인 절차'를 말합니다. 그런 점에서 우리가 학습하려는 자료구..
2018~/파이썬 자료구조 알고리즘 2019. 5. 7. 00:17
02c. 이중 연결 리스트(doubly linked list) - v. 탐색

탐색 출력과 탐색의 과정은 똑같습니다. 즉, 이 작업도 단일 연결 리스트와 동일하며 단지 head에서부터냐 tail에서부터냐로 나뉩니다. 다만 tail로 탐색해서 나온 위치(인덱스)는 초기값을 -1로 주고 진행할 때마다 1씩 감소시켜서 head로 구한 인덱스와 구분시키도록 하겠습니다.(마치 파이썬의 리스트처럼.) 코드 구현 #이중 링크드 리스트 class DLinkedList: #D_L_list에서 쓸 노드 class Node: def __init__(self, v, n = None, p = None): self.value = v #저장된 데이터 self.next = n #다음 노드 가리키는 변수 self.prev = p #이전 노드 가리키는 변수 #D_L_List에서 필요한 변수 def __init__..
2018~/파이썬 자료구조 알고리즘 2019. 5. 6. 02:38
Prev 1 2 3 4 5 Next