基礎演算法知識

一、冒泡排序

Java中耳熟能詳的演算法想必也是冒泡排序了，但是冒泡排序也是有講究滴！

時間復雜度比較差的O(n2)

int[] arrays = {2, 1, 5, 4, 3};
for (int i = 0; i < arrays.length-1; i++) {
	int i1;
	for (int i2 = 0; i2 < arrays.length-1; i2++) {
		if (arrays[i2]>arrays[i2+1]){
			i1 = arrays[i2];
			arrays[i2]=arrays[i2+1];
			arrays[i2+1]=i1;
		}
	}
}	

這是常見的冒泡排序，但是這種寫法時間復雜度是 O(n2) 也就是效率比較低下,按照冒泡排序相鄰比較這一原則上要回圈 25 次.
正序的情況下每次回圈都會把最大的放在最后一位,也就是說沒有必要做那么多無意義的比較
第一次比較的結果已經是 1,2,4,3,5 那么 3 和 5 還有比較的必要嗎?

時間復雜度比較好的O(n)

int[] arrays = {2, 1, 5, 4, 3};
for (int i = 0; i < arrays.length-1; i++) {
	int i1;
	for (int i2 = 0; i2 < arrays.length-1-i; i2++) {    //減去i!
		if (arrays[i2]>arrays[i2+1]){
			i1 = arrays[i2];
			arrays[i2]=arrays[i2+1];
			arrays[i2+1]=i1;
		}
	}
}	

不過這也引出了兩種概念, 時間復雜度 和 空間復雜度

二、時間復雜度

1、什么是時間復雜度

是指執行當前演算法所消耗的時間

2、如何計算時間復雜度

使用「 大O符號表示法 」，即 T(n) = O(f(n))
先上個栗子

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

通過「 大O符號表示法 」，這段代碼的時間復雜度為：O(n) ，為什么呢?

在 大O符號表示法中，時間復雜度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行代碼執行次數之和，而 O 表示正比例關系，這個公式的全稱是：演算法的漸進時間復雜度，

我們繼續看上面的例子，假設每行代碼的執行時間都是一樣的，我們用 1顆粒時間 來表示，那么這個例子的第一行耗時是1個顆粒時間，第三行的執行時間是 n個顆粒時間，第四行的執行時間也是 n個顆粒時間（第二行和第五行是符號，暫時忽略），那么總時間就是 1顆粒時間 + n顆粒時間 + n顆粒時間 ，即 (1+2n)個顆粒時間，即： T(n) = (1+2n)*顆粒時間，從這個結果可以看出，這個演算法的耗時是隨著n的變化而變化，因此，我們可以簡化的將這個演算法的時間復雜度表示為：T(n) = O(n)

為什么可以這么去簡化呢，因為大O符號表示法并不是用于來真實代表演算法的執行時間的，它是用來表示代碼執行時間的增長變化趨勢的，

所以上面的例子中，如果n無限大的時候，T(n) = time(1+2n)中的常量1就沒有意義了，倍數2也意義不大，因此直接簡化為T(n) = O(n) 就可以了，

（1）、常數階O(1)

無論代碼執行了多少行，只要是沒有回圈等復雜結構，那這個代碼的時間復雜度就都是O(1)

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

上述代碼在執行的時候，它消耗的時候并不隨著某個變數的增長而增長，那么無論這類代碼有多長，即使有幾萬幾十萬行，都可以用O(1)來表示它的時間復雜度，

（2）、線性階O(n)

開頭哪一個就是

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

這段代碼，for回圈里面的代碼會執行n遍，因此它消耗的時間是隨著n的變化而變化的，因此這類代碼都可以用O(n)來表示它的時間復雜度，

（3）、對數階O(logN)

先上代碼

int i = 1;
while(i<n)
{
    i = i * 2;
}

從上面代碼可以看到，在while回圈里面，每次都將 i 乘以 2，乘完之后，i 距離 n 就越來越近了，我們試著求解一下，假設回圈x次之后，i 就大于 2 了，此時這個回圈就退出了，也就是說 2 的 x 次方等于 n，那么 x = log2^n
也就是說當回圈 log2^n 次以后，這個代碼就結束了，因此這個代碼的時間復雜度為：O(logn)

（4）、線性對數階O(nlogN)

線性對數階O(nlogN) 其實非常容易理解，將時間復雜度為O(logn)的代碼回圈N遍的話，那么它的時間復雜度就是 n * O(logN)，也就是了O(nlogN)，

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

（4）、平方階O(n2)

平方階O(n2) 就更容易理解了，如果把 O(n) 的代碼再嵌套回圈一遍，它的時間復雜度就是 O(n2) 了，也就是開頭的哪個冒泡排序，

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

這段代碼其實就是嵌套了2層n回圈，它的時間復雜度就是 O(n*n)，即 O(n2)
如果將其中一層回圈的n改成m，即：

for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

那它的時間復雜度就變成了 O(m*n)

（4）、立方階O(n3)、K次方階O(n^k)

參考上面的O(n2) 去理解就好了，O(n3)相當于三層n回圈，其它的類似，

除此之外，其實還有 平均時間復雜度、均攤時間復雜度、最壞時間復雜度、最好時間復雜度 的分析方法，有點復雜，這里就不展開了，

三、空間復雜度

1、什么是空間復雜度

是指執行當前演算法需要占用多少記憶體空間

2、空間復雜度介紹

既然時間復雜度不是用來計算程式具體耗時的，那么我也應該明白，空間復雜度也不是用來計算程式實際占用的空間的，

空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的一個量度，同樣反映的是一個趨勢，我們用 S(n) 來定義，

空間復雜度比較常用的有：O(1)、O(n)、O(n2)

1、空間復雜度 O(1)

如果演算法執行所需要的臨時空間不隨著某個變數n的大小而變化，即此演算法空間復雜度為一個常量，可表示為 O(1)

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

代碼中的 i、j、m 所分配的空間都不隨著處理資料量變化，因此它的空間復雜度 S(n) = O(1)

2、空間復雜度 O(n)

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

這段代碼中，第一行new了一個陣列出來，這個資料占用的大小為n，這段代碼的2-6行，雖然有回圈，但沒有再分配新的空間，因此，這段代碼的空間復雜度主要看第一行即可，即 S(n) = O(n)

還有什么二分排序啊什么的先不說了

標籤：Java

上一篇：Java編程語言學習-Java語言概述

下一篇：007-Java中方法的使用（基礎篇）