Computer Science/알고리즘14 [알고리듬] 시간복잡도 분석(피보나치, Peasant, Hanoi, Quick sort, Merge sort) 지난주는 시간복잡도, 알고리즘을 수행하는데 걸리는 시간(running time) 어떻게 측정하는가? 알고리즘 자체가 추상적인 상태이므로, 시간 복잡도를 이용하자. 시간 복잡도 분석 = 연산의 개수 세기 >> (시간복잡도 = n에 대한 함수) n에 대한 개수를 정확하게 세는 것은 어렵다. 따라서 최악의 경우를 따짐 -> 최대 개수에 대한 상한을 분석 ◇예제. 피보나치 수열◇ : O(mn)만큼의 한 자릿수 곱셈 (안쪽 for문) >> ppt 내용 인덱스 범위 지정이 잘못됐음. if문을 써서 i 안쪽 for 문 : 상수 개+1번의 상한을 갖게 됨. // O(k+1)를 넘지 않는 빅오를 갖게 된다. >> 안쪽 for문에서 hold += hold*X[i][j]의 값이 O(mn)의 값을 가진다. 그 이유는 i와 j.. 2020. 5. 8. [알고리즘] 시간복잡도란? 빅오표기법을 사용하는 이유? 1. 시간 복잡도 2. 빅오 표기법 3. 정렬 알고리즘 시간 복잡도(Time Complexity) 시간 복잡도는 왜 필요한가? 알고리즘 中 최선의 방법을 찾기 위하여. (학교 수업을 바탕으로 생각한 그적 피셜) 우리는 알고리즘의 효율성 즉, 실행시간은 컴퓨터가 해당 알고리즘을 실행하는 속도에 의존적이다. 시간 복잡도를 이용해 최선의 방법을 찾음으로써 알고리즘의 효율성을 따질 수 있다. 알고리즘 실행속도는 코드, 언어, 컴파일러, 컴퓨터의 스펙 등 다양한 요인에 따라서 수행 시간이 달라진다. 그럼 어떻게 알고리즘 실행 시간을 측정할 수 있을까? 매 시간 알고리즘의 정확한 실행 시간을 측정하기 어렵기 때문에 우리는 알고리즘의 환경적 요인들을 날려버린다. 알고리즘의 환경적 요인을 날려버린 상황에서 우리는 알고.. 2020. 5. 8. 이전 1 2 3 다음
