목록알고리즘 강좌 (4)

반원 블로그

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
Prev 1 Next