溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

遞歸算法的時間復雜度分析

發(fā)布時間：2020-07-12 11:09:14 來源：網(wǎng)絡 閱讀：2147 作者：灰白世界 欄目：編程語言

Master定理也叫主定理。它提供了一種通過漸近符號表示遞推關系式的方法。應用Master定理可以很簡便的求解遞歸方程。

T(N)=a(N/b)+N^d
其中 n 表示原始的樣本量， a 表示子過程發(fā)生的次數(shù)，n/b 表示子過程的樣本量，d 表示除子過程其他的操作，一般為常量

  • log(b,a)<d 則遞歸算法復雜度為O(n^log(b,a))
  • log(b,a)=d 則遞歸算法復雜度為O(n^d*log(b,a))
  • log(b,a)>d 則遞歸算法復雜度為O(n^d))

例子

   /**
     * 二分查找遞歸實現(xiàn)。
     * @param srcArray  有序數(shù)組
     * @param start 數(shù)組低地址下標
     * @param end   數(shù)組高地址下標
     * @param key  查找元素
     * @return 查找元素不存在返回-1
     */
    public static int binSearch(int srcArray[], int start, int end, int key) {
        int mid = (end - start) / 2 + start;
        if (srcArray[mid] == key) {
            return mid;
        }
        if (start >= end) {
            return -1;
        } else if (key > srcArray[mid]) {
            return binSearch(srcArray, mid + 1, end, key);
        } else if (key < srcArray[mid]) {
            return binSearch(srcArray, start, mid - 1, key);
        }
        return -1;
    }

a = 2,b=2,d=0
則算法復雜度為 n^log(b,a)=n

向AI問一下細節(jié)

免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內(nèi)容。

AI
助
手