코드에서 다양한 알고리즘 분석 요소를 어떻게 얻습니까?

Question

알고리즘 분석의 기본 사항을 동료에게 설명하기 위해 프리젠 테이션을 준비 중입니다. 그 중 일부는 이전에 주제에 대한 강의를 한 적이 없지만 모든 사람들은 수학적 배경과 수학 배경을 프로그래밍하는 데 적어도 몇 년의 시간이 걸렸습니다. , 그래서 나는 이것을 가르 칠 수 있다고 생각합니다. 개념을 잘 설명 할 수는 있지만 몇 가지 코드 구조 나 패턴의 구체적인 예가 필요하므로 요소를 보여줄 수 있습니다.

기하학적 요소 (n, n^2, n^3 등)는 동일한 센티널을 사용하여 쉽게 포함 된 루프이지만, 덜 일반적인 요소를 설명하고 보여주기 위해 길을 잃어 가고 있습니다.

I는 통합하려는 지수 (2^N 또는 C^N), 대수 (N N (기록)하거나 N (로그)) 및 프레젠테이션 factoral (N!) 요인 . 코드에서 이것을 얻을 수있는 짧고, 가르침이 좋은 방법은 무엇입니까?

Answer 1

지수 : naive Fibonacci implementation과 같은 시간 문제.

N 로그 (n)이 아니면 그냥 로그 (N) : Sorting 및 Binary seach

계승 : 나이브 외판원 솔루션을 제공합니다. NP 완성 문제에 대한 많은 순진한 해결책. 의심

Answer 2

문제를 반으로 나눌 때마다 일정량의 작업을 수행하는 분할 및 정복 알고리즘은 O(log n)입니다. 예를 들어 이진 탐색.

문제를 반으로 나눌 때마다 선형 양 작업을 수행하는 분할 및 정복 알고리즘은 O(n * log n)입니다. 예를 들어 병합 정렬입니다.

지수 및 계승은 아마도 집합의 모든 하위 집합 또는 집합의 모든 순열을 반복하여 가장 잘 설명 할 수 있습니다.

Answer 3

n! 문제는 꽤 간단합니다. 많은 NP 완료 n! the travelling salesman problem

Answer 4

정렬 알고리즘 중 하나를 선택 - 모든 사람들이 어떻게해야하는지 알고 있고, 따라서 그들은 복잡한 물건에 관하여 설명하기 쉽습니다 :이 여행 세일즈맨 것을 증명 아니에요 : 괴짜를 들어 Wikipedia has a quite good overview