三个示例学习如何描述算法的运行时间

1. 准备工作

• 从数组中取出目标值所在的索引位置（数组中可能含有多个目标元素）
• 创建接口 FindElementUtil
• 创建实现类 FirstWay SecondWay ThirdWay
• 测试

import java.util.List;

public interface FindElementUtil {
    /**
     *
     * @param elements 目标数组
     * @param n 数组中的元素个数
     * @param target 查找目标
     * @return 目标值在数字中的索引位置，若没找到则返回-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;
        
        /**
         * 当前循环会执行 n 次迭代（循环体执行n次）
         * n + 1 次越界判断（每次迭代都会判断当前索引是否小于数组长度）
         */
        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 相比，迭代次数与判断次数均减少
         * 因为找到了就会立即返回
         *
         * 迭代次数：1 to n
         * 判断次数：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) {

        //将数组中的最后一个元素保存到一个局部变量中
        int lastEle = elements.get(n - 1);

        //将目标值赋值到数组的最后一个元素
        elements.set(n - 1, target);

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

        //将原本保存的最后一个元素归位
        elements.set(n - 1, lastEle);
        /**
         * 判断
         * 1. 迭代数 index 是否小于 数组长度
         * 2. 数组最后一个元素是否为目标值
         */

        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 的运行时间：

为了表示完成一项任务所花的时间，我们必须做一些简单的假设。我们假定每步单独的操作---无
论它是一个算术运算（例如加减乘除）、比较、变量赋值、给数组标记索引操作，或者程序调用、
从程序中返回结果---均会花掉不依赖于输入规模的固定时间（输入规模指的就是本例中的数组中
的元素数目），操作不同，各个操作所花费的时间也不同，例如除法操作可能比加法操作花费更长
时间。一个步骤可能含有多个简单操作，由于多个步骤所执行的操作所花费的时间不同，执行不同
步骤所花费的时间也是不一样的。

第一步 int index = -1; 和第三步 return index; 只会执行一次，但是第二步 for(){} 呢？我们必须对 i (循环增量) 和 n（数组元素数量） 的值进行比较 (i 是否小于 n），比较多少次呢？比较 n + 1 次。（for循环，从第一次开始算，每次执行一次循环体前都会执行判断条件语句）

/**
 * @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; } 执行了 n 次，当循环增量 i 从 0 变化到 n 时，对于每个 i 值，我们都执行了第 二(1) 步，我们不知道这里到底会执行多少次，因为不确定数组中有多少个目标值。所以第二步(循环)会执行两个具有不同循环次数的操作：

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

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

• 我们将第 二(1) 步中判断元素是否等于目标值的操作时间记为 T2(1)′

• 我们将第 二(1) 步中把 i 赋值给 index 的操作时间记为 T2(1)″

将 FirstWay 分为三步，约定执行第 i 步所需花费的时间为 Ti，其中 Ti 是不依赖于输入规模 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的时间 + 循环判断比较的时间 * (n + 1) + 循环增量递增的时间 * n + 判断元素是否等于目标值的时间 * n + 把i赋值为index的时间 * 一个没有则为0 + 返回的时间

• top = 定义index的时间 + 循环判断比较的时间 * (n + 1) + 循环增量递增的时间 * 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)

所以实际上这就是两个 线性函数 ，可表示成 c * n + d 的形式。其中 c 和 d 均为不依赖于 n 的常量。

所以：FirstWay 的运行时间可表示为 介于关于 n 的一个线性函数和关于 n 的另一个线性函数之间。

在算法中使用一个特殊符号来表示运行时间大于关于 n 的一个线性函数，同时小于关于 n 的另一个线性函数。将这样的运行时间表示为 θ(n)。（读：theta n）这样表示去除了低阶项(T1 + T2′ + T3) 和 n 的系数。尽管这样表示会降低精度，但是它强调了 运行时间的增长阶数，弱化了不必要的细节。
**（ ①确实，数据量低的时候，是否使用正确的算法不会对程序造成过多的影响，但是数据量较大时，正确的算法便可以提搞运行效率） **

θ 符号可以表示任何通用的函数，假如我们有两个函数，f(n) g(n) ，且当 n 足够大时，f(n) 在 g(n) 的常数倍之内，此时我们成 f(n) = θ(g(n))。

注释：f(n) 就是小时候学习xy函数时候的y，n 就是 x。
f(n) = 2x  与 y = 2x 是等价的，表示方式不同而已。

所以说 `f(n)` 在 `g(n)` 的常数倍之内的意思就是 
一个函数：f(n) = 常量 * x 的值 
在另一个函数：g(n) = 常量 * x 的值的常数倍之内。

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

y 始终在 z 的常数倍之内，（零也是常数，常数就是常量）
所以 y = θ(z)，说 z = θ(y) 也是一样的

所以说当 n 足够大时，FirstWay 的运行时间小于等于 n 的某个常数倍。

在使用 θ 符号时，我们仅仅关心 主阶项 而忽略 次阶项 和 主阶项的常量因子。也就是说 y = 2x²; 和 z = 10x²; 是等价的，忽略次阶项和主阶项的常量因子后，y和z都等于x²。所以可以说 y 和 z 都等于：θ(n²)。

假设：f(n) = n²/4 + 100n + 100 那么忽略过后：f(n) = θ(n²)

如果在思考当 n = 1 的时候，明明 100n 起到了主导作用的话，请参看 ①

2）计算 SecondWay 的运行时间

如果 elements.get(0) 等于 target，那么循环只迭代了一次。如果 elements 中没有 target，那么循环会迭代 n 次，此时称：在最坏的情况下，SecondWay 在一个包含 n 个元素的数组中进行查找操作需要花费 θ(n) 的时间（最坏情况下也是一个关于 n 的线性函数）。

在最好的情况下，当 elements.get(0) 等于 target 时，SecondWay 只会花费常量时间（因为运行时间与 n 无关，所以称之为常量时间），此时使用 θ(1) 来表示运行时间是一个不依赖于 n 的常量。

此时问题就出来了，我们不能用 θ(n) 来表示 SecondWay 的运行时间，因为在 最好情况下 SecondWay 的运行时间与 n 无关，是一个常量 θ(1)。

新概念：关于 n 的一个线性函数是所有情况的上界，使用 Ο(n) 来表示。（读：ou of n）

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

f(n) = 4n

g(n) = 2n

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

对于 SecondWay ，我们可以称在所有情况下，该算法的运行时间均满足 Ο(n)，尽管它的运行时间可能会比关于 n 的线性函数运行时间好（elements.get(0)==target 为 true 时），但是它一定不会比关于 n 的线性函数运行时间差。这就是 Ο(n) 存在的意义。

那么我们如何表示一个函数的运行时间不会比关于 n 的某个线性函数好呢？这是一个下界问题。就是如何描述下界？此时使用的是 Ω 符号，它与 Ο 符号的含义恰恰相反。

如果 f(n) 是 Ω(g(n)) ，即一旦 n 变得非常大，f(n) 的下界是 g(n) 的常数倍，就写作：f(n) = Ω(g(n))。

Ο 符号给出了上界，Ω 符号给出了下界，Θ 符号即给出了上界也给出了下界，我们能推断出：
②f(n) 是 θ(g(n))的必要条件，当且仅当 f(n) 是 Ο(g(n)) 且 f(n) 是 Ω(g(n))。

把运行时间看成一个区间，上界就表示最大值，下界表示最小值。运行时间最小，则表示速度最快，也就是最好情况。

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

使用 f(n) 表示下界，此时下界又可以使用 Ω(n) 表示，使用 g(n) 表示上界，此时上界又可
以使用 Ο(n) 表示，而 f(n) 和 g(n) 都是线性函数，Θ(n) 的定义是 运行时间大于某个线
性函数又小于某个线性函数，所以此时 就可以使用 Θ(n) 表示

所以描述 SecondWay 最恰当的方式就是给出一个满足所有情况的下界：Ω(1)，就是至少要花费常量时间。（常量运行时间就是指与 n 无关的运行时间）

Θ 、Ο、Ω 符号均为 渐近符号，这些符号记录了 随着变量近似趋向于无穷大时函数的增长趋势。这些渐近符号使得我们去掉了低阶项和高阶项的常量因子，以便淡化不必要的细节，专注于主要方面：函数是如何随着 n 增长而变化的！

3) 计算 ThirdWay 运行时间

至少会执行一次迭代，最多执行 n 次迭代。ThirdWay 和 SecondWay 最大的不同是，ThirdWay 每次迭代的时间均小于 SecondWay（少了判断数组越界）。两者最坏的情况下均需要花费线性时间（n的线性函数）。虽然 ThirdWay 的常量因子小一些，但是当我们使用 渐近符号 表示时，它们是相等的，即在最坏情况下均是 θ(n) 最好情况下均是 θ(1)，满足所有条件时均为 Ο(n)。