알고리즘의 복잡성 - 연습

저는 컴퓨터 과학 입문 과정에서 시험을 배우기 때문에 "일반"알고리즘과 재귀 알고리즘 모두에서 복잡성에 대한 문제가 있습니다. 일반적으로 C 코드로 작성된 질문).
인터넷이나 어딘가에 온라인 예제가 있는지 궁금 해서요. 기본 레벨의 주제를 다루는 책입니다.
이와 같은 적어도 질문의 수준 :

샘플 운동 alt text http://img42.imageshack.us/img42/4456/ex1j.jpg 알고리즘의 복잡성 - 연습

출처

2009-09-01 bks

가 뭔가 코먼의 책 외에? – bks

http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html –

이것과 다른 링크를보고 난 후에 나는 큰 O에 대해 알고있는 것을 알게되었다. 표기법, 간단히 말해서 2log (3.5n) + 2.4는 n만큼 log (n)과 똑같이 동작합니다. MIT 강의를 들려 줄 것입니다.하지만 다른 것이 있으면 여기에 게시하십시오. – bks

내가 Introduction to Algorithms에 아주 좋은 설명을 발견했다 ....하지만 당신은 그것을 이해하기 위해 몇 가지 수학 지식이 필요합니다.

MIT에서 Asymptotic Notation에 관한 알고리즘 개론 강의 (비디오)는 here입니다.

출처

2009-09-01 07:29:56

30 초 동안 저를 구타했습니다. Cormen, Leiserson and Rivest의 알고리즘 소개는 제가 알고있는 일반적인 알고리즘에 대한 최고의 소개입니다. –

나는 실제로 그것을 읽기 시작했다, 내가 필요로하는 것을 건드리지 만 간단히 말하면 다른 것들에 대해 더 자세히 설명한다. 그 강의에서 전리품을 드리겠습니다. – bks

큰 O 표기법은 짧습니다. 그러나이 책의 모든 알고리즘을 철저히 분석합니다. 그래서 전체 책은 예제와 연습으로 가득차 있습니다. –

Cormen, Leiserson and Rivest의 알고리즘 소개는 내가 아는 알고리즘에 대한 가장 일반적인 소개입니다.

Aho, Hopcroft 및 Ullman의 컴퓨터 알고리즘 설계 및 분석도 좋습니다. 그러나 알고리즘 소개 (Introduction to Algorithms)보다 입문 텍스트로 소화하기가 더 어렵습니다 ...

그리고 저는 Jon Bentley가 Programming Pearls를 좋아합니다. 모두가 그것을 읽어야합니다.

출처

2009-09-01 07:37:20

또한 MIT의 비디오 강의 (http://academicearth.org/courses/introduction-to-algorithms)에서 다음 비디오 강의를 따르는 것이 좋습니다.

행운을 빌어 요!

출처

2009-09-01 07:59:03

고마워요. 그걸 보겠습니다. – bks

복잡성 부분이 생길 때까지 새로운 주제로 나아 가지 않을 것입니다. 문의 할 내용은 알고리즘 소개 (Introduction to Algorithm)이 좋은 옵션입니다. 기본적으로 복잡성 Big-oh, omega 및 theta 표기법을 표현하는 세 가지 방법이 있습니다. 반복 알고리즘의 복잡성 계산은 매우 간단합니다. 어떤 책을 읽고 몇 가지 예를 연습하십시오. 재귀 알고리즘의 경우 마스터 정리을 읽습니다. 이 정리를 사용하면 대부분의 재귀 적 질문에 대한 복잡성을 쉽게 계산할 수 있습니다. net에서 master theorem을 검색하면 몇 가지 좋은 자습서를 찾을 수 있습니다. 여기에서 시작할 수 있습니다 http://en.wikipedia.org/wiki/Master_theorem.

출처

2009-09-01 08:11:38 Duleb

Cormen의 문제는, 예를 들어, 대부분 O (n) 표기법으로 번역 된 코드 분석의 최종 결과를 볼 수 있습니다. T (n) = T (2n/3) + 1, 나는 당신에게 O (n) = log (n)을 제공한다는 것을 알고 있지만 코드 자체에서 수식 (및 반복 알고리즘 수식)을 결정하는 방법에 대해 더 많은 성취가 필요합니다. 아마도 내가 틀렸고 그 책에는 내가 뭘 찾고 있는지, 답을 주셔서 감사합니다! – bks

재귀 알고리즘의 예입니다. 제가 조언을 구하는 것은 재귀가 어떻게 작동 하는지를 먼저 이해하고 마스터 정리를 통과하는 것입니다. 마스터스 정리는 거의 모든 재귀 적 문제를 해결하는 3 가지 경우를 가지고 있습니다. – Duleb

마스터 정리는 다음과 같은 형태의 되풀이 관계에 관한 것이다. T (n) = aT (n/b) + f (n) 이것은 기본적으로 우리의 문제를 하위 문제로 분해했고 각 하위 문제의 크기는 n f (n)은 하위 문제의 솔루션을 결합하여 최종 솔루션을 완성하는 데 필요한 노력을 나타냅니다. – Duleb

당신의 운동을 해결하는 공식적인 방법은 다음과 같습니다

enter image description here

이 (컴파일러가 MinGW2.95입니다) C 언어로 다음과 같은 프로그램을 실행, 확인하려면 :

#include <stdio.h> 
#include <math.h> 
int main() { 
    int sumIN = 0, sumOUT = 0; 
    double i, n = 500, j; 
    double d; 
    for (i = 1; i <= n; i ++) { 
     d = 1/(double)i; 
     j = i; 
     while (j > 0 && d > 0) { 
      j -= d; 
      sumIN ++; 
     } 
     sumOUT ++; 
    } 
    printf("\nsumIN = %d, sumOUT = %d", sumIN, sumOUT); 
    printf("\n"); 
    return 0; 
}

출처

2014-03-16 20:47:52

알고리즘의 복잡성 - 연습

답변

관련 문제