柚子快報激活碼778899分享：算法 數(shù)據(jù)結(jié)構(gòu)（1）
柚子快報激活碼778899分享：算法 數(shù)據(jù)結(jié)構(gòu)（1）
Hello~,歡迎大家來到我的博客進(jìn)行學(xué)習(xí)！
目錄
1.數(shù)據(jù)結(jié)構(gòu)2.算法3.算法效率4.復(fù)雜度4.1復(fù)雜的概念4.2 時間復(fù)雜度4.2.1 定義4.2.2 大O的漸進(jìn)表示法實戰(zhàn)：冒泡排序的時間復(fù)雜度
1.數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)(Data Structure)是計算機(jī)存儲、組織數(shù)據(jù)的方式，指相互之間存在?種或多種特定關(guān)系的數(shù)據(jù)元素的集合。沒有一種單一的數(shù)據(jù)結(jié)構(gòu)對所有用途途都有用，所以我們要學(xué)各式各樣的數(shù)據(jù)結(jié)構(gòu)，如：線性表、樹、圖、哈希等。
簡而言之：數(shù)據(jù)結(jié)構(gòu)用來存儲數(shù)據(jù)，還可以用來管理數(shù)據(jù)。 之前學(xué)過的數(shù)組為最基本的數(shù)據(jù)結(jié)構(gòu)，放同類型的數(shù)據(jù)。既然有管理的功能，我們就可以對里面的數(shù)據(jù)進(jìn)行修改，例如：添加、刪改。但是數(shù)組并不能滿足所有的需求，我們需要多種數(shù)據(jù)結(jié)構(gòu)來承載不同的數(shù)據(jù)。就好像是生活中我們需要不同的鞋子來進(jìn)行不同的運(yùn)動一樣。
2.算法
算法(Algorithm):就是定義良好的計算過程，他取一個或一組的值為輸入，并產(chǎn)生出一個或一組值作為輸出。簡單來說算法就是一系列的計算步驟，用來將輸入數(shù)據(jù)轉(zhuǎn)化成輸出結(jié)果。
簡單理解就是假設(shè)我們需要對一組整型數(shù)據(jù)進(jìn)行排序，我采用冒泡排序來完成這一功能，此時我使用的就是一個排序算法，當(dāng)然其他人可能會使用其他的方式來完成，此時就會有不同的算法，我們會依靠算法的復(fù)雜度來判斷哪一個算法比較好。
簡而言之：我們對一個問題的實現(xiàn)方法就是算法。
這里我將數(shù)據(jù)結(jié)構(gòu)和算法放在一起解釋是因為數(shù)據(jù)結(jié)構(gòu)和算法不分家，我們利用算法將數(shù)據(jù)存儲到數(shù)據(jù)結(jié)構(gòu)上，有算法的地方我們需要對數(shù)據(jù)進(jìn)行存儲和管理，此時就需要數(shù)據(jù)結(jié)構(gòu)。
3.算法效率
我們可能會想如何衡量一個算法的好壞？是看代碼的簡潔度嗎？我們可能會想遞歸看起來很簡潔，但是使用遞歸的代碼不一定就好。我們首先會想到看算法的執(zhí)行時間，當(dāng)然這是不可以的，算法的執(zhí)行時間是無法估計出來的。
舉例：
#include
int main()
{
int t1 = clock();//clock計算程序執(zhí)行開始到當(dāng)前代碼的時間
for (int i = 0; i < 100000; i++)
{
for (int j = 0; j < 100000; j++)
{
int a = 1;
}
}
int t2 = clock();
printf("%d\n", t2 - t1);//總時間
return 0;
}
運(yùn)行結(jié)果： 我們可以看到三次的時間并不相同，所以我們并不能直接指出這個算法的執(zhí)行時間。這個執(zhí)行時間與編譯器和系統(tǒng)的cpu有關(guān)。經(jīng)過實踐我們發(fā)現(xiàn)直接看程序的執(zhí)行時間是不行的。
現(xiàn)在上題目進(jìn)行理解： 輪轉(zhuǎn)數(shù)組 給定一個整數(shù)數(shù)組 nums，將數(shù)組中的元素向右輪轉(zhuǎn) k 個位置，其中 k 是非負(fù)數(shù)。 現(xiàn)在有一個數(shù)組nums，依照圖例我們可以找到輪轉(zhuǎn)的方式為（最后一個數(shù)字往前放）： 我們需要存儲最后一個數(shù)字7，并把前面的數(shù)據(jù)整體往后移動。創(chuàng)建int類型的endNum來存儲最后一個數(shù)據(jù)，我們可以利用下標(biāo)和for循環(huán)來實現(xiàn)數(shù)據(jù)的整體移動，讓nums[ i ] =nums[ i-1 ]，i 不斷的 - - ,一直到i < 0的時候結(jié)束循環(huán)。此時數(shù)字最前面的位置就空了出來，我們可以把之前存儲的endNum放到最前面。我們現(xiàn)在對一次輪轉(zhuǎn)已經(jīng)很清楚了，題目要求進(jìn)行k次輪轉(zhuǎn)，我們利用while循環(huán)，里面的條件寫k - - 就行。
代碼：
void rotate(int* nums, int numsSize, int k) {
while (k--) {
int endNum = nums[numsSize - 1];
for (int i = numsSize - 1; i > 0; i--) {
nums[i] = nums[i - 1];
}
nums[0] = endNum;
}
}
運(yùn)行結(jié)果： 提交結(jié)果： 我們的代碼在運(yùn)行時通過了，但是提交的時候卻出現(xiàn)了超出時間限制的問題，我們看看題目的提醒事項。 我們可以看到，對于nums數(shù)組的大小的范圍，里面元素大小的范圍，以及輪轉(zhuǎn)的次數(shù)的范圍。他們都是很大的數(shù)字，我們的代碼對于一些小范圍的值可以正常的運(yùn)行，對于數(shù)據(jù)比較龐大的時候我們的代碼雖然可以運(yùn)行，但是執(zhí)行速度會很慢。這表明了我們的代碼雖然可以寫出來可以運(yùn)行，但是不一定好！我們就需要復(fù)雜度來衡量算法的好壞。
4.復(fù)雜度
4.1復(fù)雜的概念
算法在編寫成可執(zhí)行程序后，運(yùn)行時需要耗費時間資源和空間(內(nèi)存)資源 。因此衡量一個算法的好 壞，一般是從時間和空間兩個維度來衡量的，即時間復(fù)雜度和空間復(fù)雜度。
時間復(fù)雜度主要衡量一個算法的運(yùn)行快慢，而空間復(fù)雜度主要衡量一個算法運(yùn)行所需要的額外空間。 在計算機(jī)發(fā)展的早期，計算機(jī)的存儲容量很小，所以對空間復(fù)雜度很是在乎。但是經(jīng)過計算機(jī)行業(yè)的 迅速發(fā)展，計算機(jī)的存儲容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個算法 的空間復(fù)雜度。
4.2 時間復(fù)雜度
4.2.1 定義
在計算機(jī)科學(xué)中，算法的時間復(fù)雜度是?個函數(shù)式T(N)，它定量描述了該算法的運(yùn)行時間。時 間復(fù)雜度是衡量程序的時間效率。
不采用程序的運(yùn)行時間的原因前文中我們已經(jīng)有提及，這里我們進(jìn)行總結(jié)：
因為程序運(yùn)行時間和編譯環(huán)境和運(yùn)行機(jī)器的配置都有關(guān)系，比如同?個算法程序，用一個老編譯 器進(jìn)行編譯和新編譯器編譯，在同樣機(jī)器下運(yùn)行時間不同同一個算法程序，用一個老低配置機(jī)器和新高配置機(jī)器，運(yùn)行時間也不同時間只能程序?qū)懞煤鬁y試，不能寫程序前通過理論思想計算評估
T(N)函數(shù)式計算了程序的執(zhí)行次數(shù)。我們知道算法程序被編譯后生成?進(jìn)制指令，程序運(yùn)行就是cpu執(zhí)行這些編譯好的指令。那么我們通過程序代碼或者理論思想計算出程序的執(zhí)行次數(shù)的函數(shù)式T(N)，假設(shè)每句指令執(zhí)行時間基本?樣(實際中有差別，但是微乎其微，這里直接忽略)，那么執(zhí)行次數(shù)和運(yùn)行時間就是等比正相關(guān)，這樣也脫離了具體的編譯運(yùn)行環(huán)境。執(zhí)行次數(shù)就可以代表程序時間效率的優(yōu)劣。
假設(shè)算法a程序T(N) = N，算法b程序T(N) = N^2，那么算法a的效率?定優(yōu)于算法b。
現(xiàn)在我們直接上實例直接運(yùn)用。 請計算?下Func1中++count語句總共執(zhí)行了多少次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
++count;
}
}
for (int k = 0; k < 2 * N; ++k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}
int count =0 ;執(zhí)行一次，第一個for循環(huán)并進(jìn)行嵌套的語句執(zhí)行 n * n 次，第二個for循環(huán)執(zhí)行2n次，但是前面一開始的語句int count =0;并不需要進(jìn)行計數(shù)，只執(zhí)行一次我們可以忽略不計，最后的while執(zhí)行10次。所以我們可以得出表達(dá)式T（n）= n ^2 +2n+10。但是我們是粗略的估計，我們并不需要給一個固定的值n，計算出一個定值。
實際中我們計算時間復(fù)雜度時，計算的也不是程序的精確的執(zhí)行次數(shù)，精確執(zhí)行次數(shù)計算起來還是很麻煩的(不同的一句程序代碼，編譯出的指令條數(shù)都是不?樣的)，計算出精確的執(zhí)行次數(shù)意義也不大，因為我們計算時間復(fù)雜度只是想比較算法程序的增長量級，也就是當(dāng)N不斷變大時T(N)的差別，上面我們已經(jīng)看到了當(dāng)N不斷變大時常數(shù)和低階項對結(jié)果的影響很小，所以我們只需要計算程序能代表增長量級的大概執(zhí)行次數(shù)，復(fù)雜度的表示通常使用大O的漸進(jìn)表示法。
4.2.2 大O的漸進(jìn)表示法
我們可以按照以下規(guī)則來推導(dǎo)大O階：
時間復(fù)雜度函數(shù)式T(N)中，只保留最高階項，去掉那些低階項，因為當(dāng)N不斷變大時，低階項對結(jié)果影響越來越小，當(dāng)N無窮大時，就可以忽略不計了。如果最高階項存在且不是1，則去除這個項目的常數(shù)系數(shù)，因為當(dāng)N不斷變大，這個系數(shù)對結(jié)果影響越來越小，當(dāng)N無窮大時，就可以忽略不計了。T(N)中如果沒有N相關(guān)的項目，只有常數(shù)項，用常數(shù)1取代所有加法常數(shù)。
根據(jù)以上規(guī)則，我們可以將T（n）= n ^2 +2n+10中的2n+10去除化為T（n）= n ^2。我們時間復(fù)雜度不能用一個函數(shù)式來精確的表示，所以我們的時間復(fù)雜度為O（n ^2），（）里面是影響當(dāng)前算法的輸入條件n。
學(xué)會之后我們可以用一些例子來練練手。 示例1
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}
Func2的時間復(fù)雜度為O（n），注意第二條規(guī)則。
示例2
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++k)
{
++count;
}
for (int k = 0; k < N; ++
k)
{
++count;
}
printf("%d\n", count);
}
T(n) = m+n;這里（n）和表達(dá)式里面的n是不一樣的，（n）是可變的輸入條件。在我們的表達(dá)式中有兩個可變的條件m和n，（n）可以表示我們表達(dá)式中的m和n。所以Func3的時間復(fù)雜度為O（m+n）。
現(xiàn)在我們對這兩個可變的條件進(jìn)行進(jìn)一步的討論，這里我們假設(shè)3個情況。 時間復(fù)雜度：
m >> n: O(m)n >> m: O(n)n == m：O(m)或O(n)
示例3
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}
Func4的時間復(fù)雜度為O（1），參考規(guī)則三。這里的1不是表示執(zhí)行一次，而是表示常數(shù)。
示例4 計算strchr的時間復(fù)雜度
const char* strchr(const char
* str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '\0')
return NULL;
p_begin++;
}
return p_begin;
}
在這里我們需要找字符在字符串中出現(xiàn)的位置。對于一個字符串a(chǎn)bcdef，我們的查找的次數(shù)的范圍為：查找一次到查找字符串的長度次。對于一個長度為n的字符串，查找最前面的字符，我們需要查找常數(shù)次；查找后面的字符我們需要查找n次；查找中間的字符，我們需要查找n/2次，利用規(guī)則2我們可以視為查找n次。 以上三種情況對我們的時間復(fù)雜度的影響還是比較大的，所以我們需要劃為三種情況來討論。
strchr的時間復(fù)雜度分為：
最好情況： O(1)最壞情況： O(N)平均情況： O(N)
通過以上的示例，我們可以做以下總結(jié)： 有些算法的時間復(fù)雜度存在最好、平均和最壞情況。
最壞情況：任意輸入規(guī)模的最大運(yùn)行次數(shù)(上界)平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界)
大O的漸進(jìn)表示法在實際中一般情況關(guān)注的是算法的上界，也就是最壞運(yùn)行情況。
只要最壞的運(yùn)行情況下時間復(fù)雜度都比較好的話，我們就可以認(rèn)為這個算法比較好。
實戰(zhàn)：冒泡排序的時間復(fù)雜度
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
冒泡排序的思想我在 有希帶你深入理解指針（2） 中已經(jīng)進(jìn)行了詳細(xì)的講解。外層的for循環(huán)控制進(jìn)行幾次冒泡排序；內(nèi)存循環(huán)控制的是當(dāng)前的冒泡，功能是比較大小然后進(jìn)行交換。這里我們是升序。 我們可以用簡單的例子進(jìn)行理解，假設(shè)我們現(xiàn)在有5個亂序的整型數(shù)字：8，4，9，3，5 這里我們可以看到外層一共是要冒四趟，內(nèi)層比較的次數(shù)每次都在減少。第一趟需要比較4次，第二趟需要比較3次，第三趟需要比較兩次，第四趟需要比較1次，我們就可以把所有的數(shù)據(jù)排完。合計需要排序的次數(shù)是4+3+2+1=10次。 如果有n個數(shù)據(jù)，需要冒泡n -1次，內(nèi)層的比較次數(shù)從n -1 依次減少，一直到1。 合計 n -1 + n - 2 + n - 3 +…+ 1= 根據(jù)規(guī)則去除低階項，去除高階項的系數(shù)，時間復(fù)雜度為O(n^2)。——最差情況 當(dāng)數(shù)據(jù)有序的時候，根據(jù)代碼會break跳出循環(huán)，只需要比較n - 1次，時間復(fù)雜度為O（n）。
示例5
void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
假設(shè) n = 8
1 < 8 cnt = 22 < 8 cnt = 44 < 8 cnt = 8
需要循環(huán)3次。 n和執(zhí)行次數(shù)(x)之間的關(guān)系為： n = 2 ^ x 所以假設(shè)為n，需要循環(huán)的次數(shù)為： 時間復(fù)雜度為：O(log2 n)
注意： 在一些書籍中，我們雖然算出是以2為底，但是書上寫的是lg n或log n （把2省略了），這在數(shù)學(xué)中是不對的。但是在數(shù)據(jù)結(jié)構(gòu)中是正確的。當(dāng)n接近無窮大時，底數(shù)的大小對結(jié)果影響不大。因此，一般情況下不管底數(shù)是多少都可以省略不寫，即可以表示為 log n。
示例6 計算階乘遞歸Fac的時間復(fù)雜度
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
遞歸開始時會創(chuàng)建當(dāng)前的函數(shù)棧幀，n不等于0會繼續(xù)向下遞歸，調(diào)用Fac（n - 1），此時又創(chuàng)建一個函數(shù)棧幀同時前面一個函數(shù)棧幀并沒有銷毀，往后的道理是一樣的。一直創(chuàng)建到n為0的函數(shù)棧幀。創(chuàng)建的次數(shù)就是遞歸調(diào)用的執(zhí)行次數(shù)，遞歸調(diào)用多少次就是最終的執(zhí)行次數(shù)。合計為n次，所以時間復(fù)雜度為O（n）。 總結(jié)·：在階乘算法中，時間復(fù)雜度即遞歸調(diào)用的次數(shù)。
好了，我們的數(shù)據(jù)結(jié)構(gòu)知識就講到這里。如果文章內(nèi)容有誤，請大佬在評論區(qū)斧正！謝謝大家！
柚子快報激活碼778899分享：算法 數(shù)據(jù)結(jié)構(gòu)（1）
精彩內(nèi)容
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Tokopedia印尼外貿(mào)購
