/**
     * 找出给定数组中目标元素的位置，如果找不到返回-1
     * @param arr 给定数组
     * @param target 目标元素
     * @return
     */
    public int find(int[] arr, int target) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // 依次遍历数组，如果找到和目标元素相同的值，在返回该值的数组下标
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

分析：目标元素在数组中位置的不同导致时间复杂度的不同。

2.2.1 最好情况时间复杂度

目标元素刚好在数组第一个位置，那么只需要一次就能找到，时间复杂度很明显是常数阶 O(1) 。

2.2.2 最坏情况时间复杂度

目标元素在数组最后一个位置或者不在数组中，那么得需要遍历完整个数组才能得出结果，时间复杂度为 O(n) 。

最坏情况运行时间是在任何输入下运行时间的一个上限。通常，除非特别指定，我们提到的运行时间都是最坏情况运行时间。

2.2.3 平均时间复杂度

可以看出，由于目标元素位置的不同，导致时间复杂度出现量级差异。这种情况下就需要考虑平均时间复杂度。

下面简单分析下：目标元素如果在数组中，出现的位置有n种情况，加上不在数组中这一种情况，总共n+1种情况。每种情况下需要遍历的次数如下表：

由上表可以得出，平均遍历次数 = 各种情况遍历次数相加 ÷ 总的情况数。
即遍历次数f(n)与数据规模之间的关系为：f(n) = (1+2+3+…+n+n) / (n+1) = [n(n+3)] / [2(n+1)]
根据大O分析法，忽略低阶项和系数得，T(n) = O(f(n)) = O(n)
因此，平均时间复杂度为：O(n)。
平均时间复杂度是所有情况中最有意义的，因为它是期望的运行时间。

2.2.4 均摊时间复杂度

均摊时间复杂度，就是把量级高的操作所耗费的时间分担到量级低的操作上，看平摊后的量级是多少。是平均时间复杂度的补充。

均摊时间复杂度应用的场景：对一个数据结构进行一组连续操作，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，适合运用均摊时间复杂度分析代码，而此时均摊时间复杂度就等于最好情况时间复杂度。

示例：这段代码实现了往数据中插入数据的功能。当数组没有满的时候，直接插入数据到数组中。当数组满了以后，遍历数组求和，将求和之后的sum值放在数组中的第一位置，然后把count指针指向索引为1的位置，再将新的数据插入。

 // array 表示一个长度为 n 的数组
 // 代码中的 array.length 就等于 n
 int[] array = new int[n];
 int count = 0;
 
 public void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
int n = i * j;

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}