算法的複雜性 - 練習

我正在學習計算機科學入門課程中的考試，並且在「常規」算法和遞歸算法中都存在複雜性問題（通常我們得到這些問題寫成C代碼）。
我想知道是否有互聯網和/或在基本層面（不是太基本）的主題的書中的在線示例。
至少像這樣的問題的水平：

樣品鍛鍊 alt text http://img42.imageshack.us/img42/4456/ex1j.jpg 算法的複雜性 - 練習

來源

2009-09-01 bks

是什麼除了科爾曼的書嗎？ – bks 2009-09-01 07:33:24

http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html – 2009-09-01 08:18:53

在看了這個以及我得到的其他鏈接後，我認爲我知道大O符號，簡而言之：2log（3.5n）+ 2.4的行爲與log（n）的行爲完全相似，足夠大。我想我會看看麻省理工學院的講座，但如果你有其他的東西，請在這裏發帖 – bks 2009-09-01 08:37:53

我已經找到了一個很好的解釋在Introduction to Algorithms ....但你需要一些數學知識去了解它。

麻省理工學院關於算法介紹課程的演講（視頻）是關於漸近表示法的是here。

來源

2009-09-01 07:29:56

你擊敗了我30秒。 Cormen，Leiserson和Rivest算法簡介是我所瞭解的一般算法的最佳介紹。 – 2009-09-01 07:31:27

我其實已經開始閱讀它，它觸及了我所需要的，但是簡要地說，然後闡述了其他的東西。我會在那場演講中拿出一個贓物，謝謝 – bks 2009-09-01 07:32:20

大O符號的簡介很簡短。但是，本書中的每個算法都經過了徹底的分析。所以整本書都充滿了例子和練習。 – 2009-09-01 07:34:54

Cormen，Leiserson和Rivest算法簡介是我所瞭解的算法中最好的一般介紹。

由Aho，Hopcroft和Ullman設計和分析計算機算法也很好。但作爲介紹性文本比算法簡介更難消化...

而且我喜歡Jon Bentley編程珍珠。每個人都應該閱讀它。

來源

2009-09-01 07:37:20

我還會推薦以下MIT的這些視頻講座：http://academicearth.org/courses/introduction-to-algorithms。

祝你好運！

來源

2009-09-01 07:59:03

謝謝，我會看看 – bks 2009-09-01 08:23:02

我的第一個建議是，在獲得 Complexity部分之前，不要繼續前進到新的主題。至於要諮詢的文字，Cormen的算法介紹是一個不錯的選擇。查看基本上有三種方式來表達複雜性大哦，歐米茄和theta符號。迭代算法的複雜度計算非常簡單。閱讀任何書並練習一些例子。遞歸算法讀取碩士定理。使用這個定理，您可以輕鬆計算大多數遞歸問題的複雜度。在網上搜索主人定理，你會發現幾個很好的教程。你可以從這裏開始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 2009-09-01 08:22:05

這是一個遞歸算法的例子。我會建議的是，首先了解遞歸如何工作，然後通過主人定理。馬斯特定理有三種情況可以解決幾乎所有的遞歸問題。 – Duleb 2009-09-01 09:41:33

主定理涉及形式的遞歸關係： T（n）= aT（n/b）+ f（n）這基本上意味着我們已經將問題分解爲子問題並且每個子問題的大小爲n/b。這裏f（n）表示結合子問題的解決方案以獲得最終完整解決方案所需的努力。 – Duleb 2009-09-01 09:44:51

解決您的鍛鍊的正式的辦法是：

enter image description here

爲了驗證，在C語言中執行以下程序（編譯器MinGW2.95）：

#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

算法的複雜性 - 練習

回答

相關問題