三個示例學(xué)習(xí)如何描述算法的運行時間

1. 準備工作

• 從數(shù)組中取出目標值所在的索引位置（數(shù)組中可能含有多個目標元素）
• 創(chuàng)建接口 FindElementUtil
• 創(chuàng)建實現(xiàn)類 FirstWay SecondWay ThirdWay
• 測試

import java.util.List;

public interface FindElementUtil {
    /**
     *
     * @param elements 目標數(shù)組
     * @param n 數(shù)組中的元素個數(shù)
     * @param target 查找目標
     * @return 目標值在數(shù)字中的索引位置，若沒找到則返回-1
     */
    int findEle(List<Integer> elements, int n, int target);
}

import java.util.List;

/**
 * @author : zyf
 * @since : 2018-12-17 23:19
 **/
public class FirstWay implements FindElementUtil {
    @Override
    public int findEle(List<Integer> elements, int n, int target) {
        int index = -1;
        
        /**
         * 當(dāng)前循環(huán)會執(zhí)行 n 次迭代（循環(huán)體執(zhí)行n次）
         * n + 1 次越界判斷（每次迭代都會判斷當(dāng)前索引是否小于數(shù)組長度）
         */
        for (int i = 0; i < n; i++) {
            if(elements.get(i) == target){
                index = i;
            }
        }
        return index;
    }
}

import java.util.List;

/**
 * @author : zyf
 * @since : 2018-12-17 23:22
 **/
public class SecondWay implements FindElementUtil {
    @Override
    public int findEle(List<Integer> elements, int n, int target) {
        
        /**
         * 與 FirstWay 相比，迭代次數(shù)與判斷次數(shù)均減少
         * 因為找到了就會立即返回
         *
         * 迭代次數(shù)：1 to n
         * 判斷次數(shù)：0 to n-1
         */
        for (int i = 0; i < n; i++) {
            if(elements.get(i) == target){
                return i;
            }
        }
        return -1;
    }
}

import java.util.List;

/**
 * @author : zyf
 * @since : 2018-12-17 23:27
 **/
public class ThirdWay implements FindElementUtil {
    @Override
    public int findEle(List<Integer> elements, int n, int target) {

        //將數(shù)組中的最后一個元素保存到一個局部變量中
        int lastEle = elements.get(n - 1);

        //將目標值賦值到數(shù)組的最后一個元素
        elements.set(n - 1, target);

        int index = 0;
        while (elements.get(index) != target) {
            index++;
        }

        //將原本保存的最后一個元素歸位
        elements.set(n - 1, lastEle);
        /**
         * 判斷
         * 1. 迭代數(shù) index 是否小于 數(shù)組長度
         * 2. 數(shù)組最后一個元素是否為目標值
         */

        if (index < n - 1 || elements.get(n - 1) == target) {
            //說明找到了
            return index;
        } else {
            //沒找到則賦值為 -1
            index = -1;
        }

        return index;
    }
}

import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.function.Function;

/**
 * @author : zyf
 * @since : 2018-12-17 23:19
 **/
public class Main {
    private static List<Integer> elements;

    public static void main(String[] args) {

        initData();

        speedMeasure(new FirstWay());
        speedMeasure(new SecondWay());
        speedMeasure(new ThirdWay());

    }

    private static void initData() {
        elements = new ArrayList<>();
        
        Random random = new Random(50);

        for (int i = 0; i <= 800000; i++) {
            int anInt = random.nextInt();
            elements.add(anInt);
        }
    }

    private static void speedMeasure(FindElementUtil util) {


        long start = System.currentTimeMillis();

        int index = util.findEle(elements, elements.size(), 500000);

        long end = System.currentTimeMillis();

        long timeCost = end - start;

        System.out.println(util.getClass().getSimpleName() + "-------timeCost：" + timeCost + "     index=" + index);
    }
}

2. 如何描述運行時間

1）計算 FirstWay 的運行時間：

為了表示完成一項任務(wù)所花的時間，我們必須做一些簡單的假設(shè)。我們假定每步單獨的操作---無
論它是一個算術(shù)運算（例如加減乘除）、比較、變量賦值、給數(shù)組標記索引操作，或者程序調(diào)用、
從程序中返回結(jié)果---均會花掉不依賴于輸入規(guī)模的固定時間（輸入規(guī)模指的就是本例中的數(shù)組中
的元素數(shù)目），操作不同，各個操作所花費的時間也不同，例如除法操作可能比加法操作花費更長
時間。一個步驟可能含有多個簡單操作，由于多個步驟所執(zhí)行的操作所花費的時間不同，執(zhí)行不同
步驟所花費的時間也是不一樣的。

第一步 int index = -1; 和第三步 return index; 只會執(zhí)行一次，但是第二步 for(){} 呢？我們必須對 i (循環(huán)增量) 和 n（數(shù)組元素數(shù)量） 的值進行比較 (i 是否小于 n），比較多少次呢？比較 n + 1 次。（for循環(huán)，從第一次開始算，每次執(zhí)行一次循環(huán)體前都會執(zhí)行判斷條件語句）

/**
 * @author : zyf
 * @since : 2018-12-18 00:39
 **/
public class Test {
    public static void main(String[] args) {
        //不會輸出
        //所以比較了 一次
        //所以一定會比較 n + 1 次
        // 0 + 1 = 1
        for (int i = 0; i < 0; i++) {
            System.out.println(1);
        }
    }
}

第 二(1) 步 if(elements.get(i) == target){ index = i; } 執(zhí)行了 n 次，當(dāng)循環(huán)增量 i 從 0 變化到 n 時，對于每個 i 值，我們都執(zhí)行了第 二(1) 步，我們不知道這里到底會執(zhí)行多少次，因為不確定數(shù)組中有多少個目標值。所以第二步(循環(huán))會執(zhí)行兩個具有不同循環(huán)次數(shù)的操作：

• 比較：n + 1 次 使用 T2′ 表示

• 遞增：n 次 使用 T2″ 表示

• 我們將第 二(1) 步中判斷元素是否等于目標值的操作時間記為 T2(1)′

• 我們將第 二(1) 步中把 i 賦值給 index 的操作時間記為 T2(1)″

將 FirstWay 分為三步，約定執(zhí)行第 i 步所需花費的時間為 Ti，其中 Ti 是不依賴于輸入規(guī)模 n 的常量。

所以 FirstWay 的運行時間介于以下 bottom 和 top 之間。

• bottom = T1 + T2′ * (n + 1) + T2″ * n + T2(1)′ * n + T2(1)″ * 0 + T3
• top = T1 + T2′ * (n + 1) + T2″ * n + T2(1)′ * n + T2(1)″ * n + T3

• bottom = 定義index的時間 + 循環(huán)判斷比較的時間 * (n + 1) + 循環(huán)增量遞增的時間 * n + 判斷元素是否等于目標值的時間 * n + 把i賦值為index的時間 * 一個沒有則為0 + 返回的時間

• top = 定義index的時間 + 循環(huán)判斷比較的時間 * (n + 1) + 循環(huán)增量遞增的時間 * n + 判斷元素是否等于目標值的時間 * n + 把i賦值為index的時間 * 所有元素均為目標值則為n + 返回的時間

乘法分配律后：

• bottom = (T2′ + T2″ + T2(1)′) * n + (T1 + T2′ + T3)
• top = (T2′ + T2″ + T2(1)′ + T2(1)″) * n + (T1 + T2′ + T3)

所以實際上這就是兩個 線性函數(shù) ，可表示成 c * n + d 的形式。其中 c 和 d 均為不依賴于 n 的常量。

所以：FirstWay 的運行時間可表示為 介于關(guān)于 n 的一個線性函數(shù)和關(guān)于 n 的另一個線性函數(shù)之間。

在算法中使用一個特殊符號來表示運行時間大于關(guān)于 n 的一個線性函數(shù)，同時小于關(guān)于 n 的另一個線性函數(shù)。將這樣的運行時間表示為 θ(n)。（讀：theta n）這樣表示去除了低階項(T1 + T2′ + T3) 和 n 的系數(shù)。盡管這樣表示會降低精度，但是它強調(diào)了 運行時間的增長階數(shù)，弱化了不必要的細節(jié)。
**（ ①確實，數(shù)據(jù)量低的時候，是否使用正確的算法不會對程序造成過多的影響，但是數(shù)據(jù)量較大時，正確的算法便可以提搞運行效率） **

θ 符號可以表示任何通用的函數(shù)，假如我們有兩個函數(shù)，f(n) g(n) ，且當(dāng) n 足夠大時，f(n) 在 g(n) 的常數(shù)倍之內(nèi)，此時我們成 f(n) = θ(g(n))。

注釋：f(n) 就是小時候?qū)W習(xí)xy函數(shù)時候的y，n 就是 x。
f(n) = 2x  與 y = 2x 是等價的，表示方式不同而已。

所以說 `f(n)` 在 `g(n)` 的常數(shù)倍之內(nèi)的意思就是 
一個函數(shù)：f(n) = 常量 * x 的值 
在另一個函數(shù)：g(n) = 常量 * x 的值的常數(shù)倍之內(nèi)。

f(n) = y = 4x
g(n) = z = x

y 始終在 z 的常數(shù)倍之內(nèi)，（零也是常數(shù)，常數(shù)就是常量）
所以 y = θ(z)，說 z = θ(y) 也是一樣的

所以說當(dāng) n 足夠大時，FirstWay 的運行時間小于等于 n 的某個常數(shù)倍。

在使用 θ 符號時，我們僅僅關(guān)心 主階項 而忽略 次階項 和 主階項的常量因子。也就是說 y = 2x2; 和 z = 10x2; 是等價的，忽略次階項和主階項的常量因子后，y和z都等于x2。所以可以說 y 和 z 都等于：θ(n2)。

假設(shè)：f(n) = n2/4 + 100n + 100 那么忽略過后：f(n) = θ(n2)

如果在思考當(dāng) n = 1 的時候，明明 100n 起到了主導(dǎo)作用的話，請參看 ①

2）計算 SecondWay 的運行時間

如果 elements.get(0) 等于 target，那么循環(huán)只迭代了一次。如果 elements 中沒有 target，那么循環(huán)會迭代 n 次，此時稱：在最壞的情況下，SecondWay 在一個包含 n 個元素的數(shù)組中進行查找操作需要花費 θ(n) 的時間（最壞情況下也是一個關(guān)于 n 的線性函數(shù)）。

在最好的情況下，當(dāng) elements.get(0) 等于 target 時，SecondWay 只會花費常量時間（因為運行時間與 n 無關(guān)，所以稱之為常量時間），此時使用 θ(1) 來表示運行時間是一個不依賴于 n 的常量。

此時問題就出來了，我們不能用 θ(n) 來表示 SecondWay 的運行時間，因為在 最好情況下 SecondWay 的運行時間與 n 無關(guān)，是一個常量 θ(1)。

新概念：關(guān)于 n 的一個線性函數(shù)是所有情況的上界，使用 Ο(n) 來表示。（讀：ou of n）

如果一個函數(shù) f(n) 是 Ο(g(n)) （意思就是 一旦 n 非常大，一個函數(shù)的上界 是另一個函數(shù)的常量因子倍）

f(n) = 4n

g(n) = 2n

則 f(n) 是 g(n) 的 1/2 倍，1/2就是常量因子

對于 SecondWay ，我們可以稱在所有情況下，該算法的運行時間均滿足 Ο(n)，盡管它的運行時間可能會比關(guān)于 n 的線性函數(shù)運行時間好（elements.get(0)==target 為 true 時），但是它一定不會比關(guān)于 n 的線性函數(shù)運行時間差。這就是 Ο(n) 存在的意義。

那么我們?nèi)绾伪硎疽粋€函數(shù)的運行時間不會比關(guān)于 n 的某個線性函數(shù)好呢？這是一個下界問題。就是如何描述下界？此時使用的是 Ω 符號，它與 Ο 符號的含義恰恰相反。

如果 f(n) 是 Ω(g(n)) ，即一旦 n 變得非常大，f(n) 的下界是 g(n) 的常數(shù)倍，就寫作：f(n) = Ω(g(n))。

Ο 符號給出了上界，Ω 符號給出了下界，Θ 符號即給出了上界也給出了下界，我們能推斷出：
②f(n) 是 θ(g(n))的必要條件，當(dāng)且僅當(dāng) f(n) 是 Ο(g(n)) 且 f(n) 是 Ω(g(n))。

把運行時間看成一個區(qū)間，上界就表示最大值，下界表示最小值。運行時間最小，則表示速度最快，也就是最好情況。

解釋一下②
f(n) = 5n
g(n) = 7n

使用 f(n) 表示下界，此時下界又可以使用 Ω(n) 表示，使用 g(n) 表示上界，此時上界又可
以使用 Ο(n) 表示，而 f(n) 和 g(n) 都是線性函數(shù)，Θ(n) 的定義是 運行時間大于某個線
性函數(shù)又小于某個線性函數(shù)，所以此時 就可以使用 Θ(n) 表示

所以描述 SecondWay 最恰當(dāng)?shù)姆绞骄褪墙o出一個滿足所有情況的下界：Ω(1)，就是至少要花費常量時間。（常量運行時間就是指與 n 無關(guān)的運行時間）

Θ 、Ο、Ω 符號均為 漸近符號，這些符號記錄了 隨著變量近似趨向于無窮大時函數(shù)的增長趨勢。這些漸近符號使得我們?nèi)サ袅说碗A項和高階項的常量因子，以便淡化不必要的細節(jié)，專注于主要方面：函數(shù)是如何隨著 n 增長而變化的！

3) 計算 ThirdWay 運行時間

至少會執(zhí)行一次迭代，最多執(zhí)行 n 次迭代。ThirdWay 和 SecondWay 最大的不同是，ThirdWay 每次迭代的時間均小于 SecondWay（少了判斷數(shù)組越界）。兩者最壞的情況下均需要花費線性時間（n的線性函數(shù)）。雖然 ThirdWay 的常量因子小一些，但是當(dāng)我們使用 漸近符號 表示時，它們是相等的，即在最壞情況下均是 θ(n) 最好情況下均是 θ(1)，滿足所有條件時均為 Ο(n)。