|
排序 （１）快速排序：快速排序是由冒泡排序改進(jìn)的，冒泡排序過程中，只對(duì)相鄰的兩個(gè)記錄進(jìn)行比較，因此每次交換兩個(gè)相鄰記錄時(shí)只能消除一個(gè)逆序．快速排序是通過兩個(gè)不相鄰記錄的一次交換消除多個(gè)逆序，提高排序速度． 時(shí)間復(fù)雜度分析：從快速排序算法的遞歸樹可知，快速排序的趟數(shù)取決于遞歸樹的深度．最好情況下：每一趟排序后都能將記錄序列均勻的分割成兩個(gè)長度大致相等的子表時(shí)間復(fù)雜度為O(nlogn)．最壞情況下：在待排序序列已經(jīng)排好序 的情況下，其遞歸樹成為單支樹．時(shí)間復(fù)雜度為O(n^2/2) 空間復(fù)雜度：快速排序是遞歸的，執(zhí)行時(shí)需要一個(gè)棧來存放相應(yīng)的數(shù)據(jù)，最大遞歸調(diào)用次數(shù)與遞歸樹的深度一致，故最好情況的空間復(fù)雜度為O(logn),最壞情況為O(n); 算法特點(diǎn)：記錄的非順次的移動(dòng)導(dǎo)致排序方法不穩(wěn)定． 排序過程中需要定位表的上階和下界，所以適合用于順序結(jié)構(gòu)，很難用于鏈?zhǔn)浇Y(jié)構(gòu)． 適合用于初始記錄無序，n較大的情況． 計(jì)算機(jī)網(wǎng)絡(luò) 層次結(jié)構(gòu)：
以五層結(jié)構(gòu)為例：應(yīng)用層，傳輸層(運(yùn)輸層)，網(wǎng)絡(luò)層，數(shù)據(jù)鏈路層，物理層 ?。保锢韺樱和ㄟ^光纖和電纜以及雙絞線等物體將計(jì)算機(jī)連接。然后才能進(jìn)行通信在計(jì)算機(jī)之間傳輸0，1這樣的電信號(hào)． ?。玻?dāng)?shù)據(jù)鏈路層：工作在物理層之上，負(fù)責(zé)給這些0，1制定傳送的規(guī)則，然后另一方再按照相應(yīng)的規(guī)則來進(jìn)行解讀。負(fù)責(zé)分配MAC地址 以太網(wǎng)協(xié)議：以太網(wǎng)協(xié)議規(guī)定，一組電信號(hào)構(gòu)成一個(gè)數(shù)據(jù)包，把這個(gè)數(shù)據(jù)包稱之為“楨”。每一個(gè)楨由標(biāo)頭(Head)和數(shù)據(jù)(Data)兩部分組成，楨的最大長度是1518個(gè)字節(jié)，最小長度為64字節(jié)。假如需要傳送的數(shù)據(jù)很大的 話，就分成多個(gè)楨來進(jìn)行傳送。 MAC地址：連入網(wǎng)絡(luò)的每一個(gè)計(jì)算機(jī)都會(huì)有網(wǎng)卡接口，每一個(gè)網(wǎng)卡都會(huì)一個(gè)地址，這個(gè)地址就叫做MAC地址。計(jì)算機(jī)之間的數(shù)據(jù)傳送，就是通過MAC地址來唯一尋找、傳送的。 ARP協(xié)議：通過它我們可以知道子網(wǎng)中其他計(jì)算機(jī)的MAC地址。 ?。常W(wǎng)絡(luò)層：實(shí)際上我們所處的網(wǎng)絡(luò)，是由無數(shù)個(gè)子網(wǎng)絡(luò)構(gòu)成的。廣播的時(shí)候，也只有同一個(gè)子網(wǎng)里面的計(jì)算機(jī)能夠收到。 假如沒有子網(wǎng)這種劃分的話，計(jì)算機(jī)A發(fā)一個(gè)數(shù)據(jù)包給計(jì)算機(jī)B,其他所有計(jì)算機(jī)也都能收到這個(gè)數(shù)據(jù)包，然后進(jìn)行對(duì)比再舍棄。世界上有那么多它計(jì)算機(jī)，每一臺(tái)計(jì)算機(jī)都能收到其他所有計(jì)算機(jī)的數(shù)據(jù)包，那就不得了了。如何區(qū)分哪些MAC地址是屬于同一個(gè)子網(wǎng)的呢？假如是同一個(gè)子網(wǎng)，那我們就用廣播的形式把數(shù)據(jù)傳送給對(duì)方，如果不是同一個(gè)子網(wǎng)的，我們就會(huì)把數(shù)據(jù)發(fā)給網(wǎng)關(guān)，讓網(wǎng)關(guān)進(jìn)行轉(zhuǎn)發(fā)。為了解決這個(gè)問題我們引入了一套新的地址協(xié)議（IP協(xié)議），這個(gè)地址協(xié)議能夠幫助我們區(qū)分MAC地址是否處于同一個(gè)子網(wǎng)中。這也是網(wǎng)絡(luò)層負(fù)責(zé)解決的問題。 ?。矗畟鬏攲樱河?jì)算機(jī)A已經(jīng)可以發(fā)送數(shù)據(jù)到計(jì)算機(jī)B中了，但是計(jì)算機(jī)B里面有多種多樣的程序應(yīng)用，此時(shí)通過指定端口Port供特定的應(yīng)用程序來接受處理．傳輸層的功能就是建立端口到端口的通信。相比網(wǎng)絡(luò)層的功能是建立主機(jī)到主機(jī)的通信。傳輸層最常見的兩大協(xié)議是 TCP 協(xié)議和 UDP 協(xié)議，其中 TCP 協(xié)議與 UDP 最大的不同就是 TCP 提供可靠的傳輸，而 UDP 提供的是不可靠傳輸。 ５．應(yīng)用層：傳過來的數(shù)據(jù)格式不同，而應(yīng)用層的功能，就是用來規(guī)定應(yīng)用程序的數(shù)據(jù)格式的． 協(xié)議有：HTTP、SMTP、FTP、ping、telnet、DNS、DHCP等 HTTP的狀態(tài)碼有哪些： ?。ǎ保?00 請(qǐng)求成功 ４開頭表示客戶端錯(cuò)誤 ?。ǎ玻?00請(qǐng)求有語法錯(cuò)誤，不能被服務(wù)器所理解； （３）：404請(qǐng)求資源不存在 ?。甸_頭表示服務(wù)器端錯(cuò)誤 ?。ǎ矗?00服務(wù)器發(fā)生不可預(yù)期的錯(cuò)誤； （５）：503服務(wù)器不能處理客戶請(qǐng)求 HTTP的長連接和短短連接： HTTP協(xié)議是基于請(qǐng)求/響應(yīng)模式的，因此只要服務(wù)端給了響應(yīng)，本次HTTP連接就結(jié)束了，或者更準(zhǔn)確的說，是本次HTTP請(qǐng)求就結(jié)束了，所謂的HTTP連接本質(zhì)上是TCP的連接。TCP連接是可以保持一段時(shí)間不中斷的就是長連接，發(fā)起一次請(qǐng)求后就主動(dòng)斷開的就是短連接，所以就有了長連接和短連接一說。 若沒有長連接TCP連接將會(huì)越來越多，直到把服務(wù)器的TCP連接數(shù)量撐爆到上限為止，長連接為了節(jié)省連接而重復(fù)利用 TCP與UDP： TCP:（１）面向連接的，每條TCP連接只能由兩個(gè)端點(diǎn)，一對(duì)一通信； ?。ǎ玻┨峁┛煽康慕桓斗?wù)，傳輸數(shù)據(jù)無差錯(cuò)，不丟失，不重復(fù)，且按時(shí)序到達(dá) （３）面向字節(jié)流，TCP根據(jù)對(duì)方給出的窗口和當(dāng)前的網(wǎng)絡(luò)擁塞程度決定一個(gè)報(bào)文應(yīng)該包含多少個(gè)字節(jié) UDP：（１）無連接，UDP使用盡最大努力交付，不保證可靠性UDP是面向報(bào)文的 ?。ǎ玻︰DP支持一對(duì)一，一對(duì)多，多對(duì)一和多對(duì)多的交互通信。 （３）應(yīng)用層交給UDP多長的報(bào)文，UDP就照樣發(fā)送，即一次發(fā)送一個(gè)報(bào)文； TCP協(xié)議需要三次握手通信成功后進(jìn)行建立，應(yīng)用場景：互聯(lián)網(wǎng)和企業(yè)網(wǎng)上客戶端應(yīng)用，數(shù)據(jù)傳輸性能讓位于數(shù)據(jù)傳輸?shù)耐暾?，可控制性和可靠性?/p> UDP協(xié)議是直接發(fā)送，不會(huì)判斷是否接收和發(fā)送成功，應(yīng)用場景：當(dāng)強(qiáng)調(diào)輸出性能而非完整性時(shí)，如音頻和多媒體的應(yīng)用。 URL與URI的區(qū)別： URI：通一資源標(biāo)志符(Universal Resource Identifier， URI)，表示是一個(gè)網(wǎng)絡(luò)資源，如 HTML文檔、圖像、視頻片段、程序等都由一個(gè)URI進(jìn)行定位的。 組成部分：訪問資源的命名機(jī)制，存放資源的主機(jī)名，資源自身的名稱 URL：是Uniform Resource Locator，表示是一個(gè)地址，URL是URI的子集，所有的URL都是URI，但不是每個(gè)URI都是URL，還有可能是URN URN:統(tǒng)一資源名稱 (Uniform Resource Name, URN)，是URI兩種形式之一。唯一標(biāo)識(shí)一個(gè)實(shí)體的標(biāo)識(shí)符，但是不能給出實(shí)體的位置 從輸入U(xiǎn)RL到展示網(wǎng)頁全過程： ?。ǎ保┹斎刖W(wǎng)址：緩存解析 瀏覽器獲取了這個(gè)url，當(dāng)然就去解析了，它先去緩存當(dāng)中看看有沒有，從 瀏覽器緩存-系統(tǒng)緩存-路由器緩存 當(dāng)中查看，如果有從緩存當(dāng)中顯示頁面，否則進(jìn)行下一步． ?。ǎ玻〥NS解析：在發(fā)送http請(qǐng)求前，需要域名解析(DNS解析)，解析獲取相應(yīng)的IP地址． ?。ǎ常g覽器向服務(wù)器發(fā)起tcp連接，與瀏覽器建立tcp三次握手。 ?。ǎ矗┪帐殖晒?，瀏覽器向服務(wù)器發(fā)送http請(qǐng)求，請(qǐng)求數(shù)據(jù)包。 （５）服務(wù)器處理收到的請(qǐng)求，將數(shù)據(jù)返回至瀏覽器 （６）瀏覽器收到HTTP響應(yīng)，讀取頁面內(nèi)容，瀏覽器渲染，解析html源碼 TCP三次握手過程： step1:建立連接時(shí)，客戶端發(fā)送SYN包到服務(wù)器，其中包含客戶端的初始序號(hào)seq=x，并進(jìn)入SYN_SENT狀態(tài)，等待服務(wù)器確認(rèn)。（其中，SYN=1，ACK=0，表示這是一個(gè)TCP連接請(qǐng)求數(shù)據(jù)報(bào)文；序號(hào)seq=x，表明傳輸數(shù)據(jù)時(shí)的第一個(gè)數(shù)據(jù)字節(jié)的序號(hào)是x）。 step2:服務(wù)器收到請(qǐng)求后，必須確認(rèn)客戶的數(shù)據(jù)包。同時(shí)自己也發(fā)送一個(gè)SYN包，即SYN ACK包，此時(shí)服務(wù)器進(jìn)入SYN_RECV狀態(tài)。（其中確認(rèn)報(bào)文段中，標(biāo)識(shí)位SYN=1，ACK=1，表示這是一個(gè)TCP連接響應(yīng)數(shù)據(jù)報(bào)文，并含服務(wù)端的初始序號(hào)seq(服務(wù)器)=y，以及服務(wù)器對(duì)客戶端初始序號(hào)的確認(rèn)號(hào)ack(服務(wù)器)=seq(客戶端) 1=x 1）。 第三步：客戶端收到服務(wù)器的SYN ACK包，向服務(wù)器發(fā)送一個(gè)序列號(hào)(seq=x 1)，確認(rèn)號(hào)為ack(客戶端)=y 1，Server檢查ack是否為x 1，ACK是否為1，如果正確則連接建立成功,完成三次握手. 總結(jié)：第三次握手是為了防止：如果客戶端遲遲沒有收到服務(wù)器返回確認(rèn)報(bào)文，這時(shí)會(huì)放棄連接，重新啟動(dòng)一條連接請(qǐng)求，但問題是：服務(wù)器不知道客戶端沒有收到，所以他會(huì)收到兩個(gè)連接，浪費(fèi)連接開銷。如果每次都是這樣，就會(huì)浪費(fèi)多個(gè)連接開銷。 四次揮手過程： 所謂四次揮手（Four-Way Wavehand）即終止TCP連接，就是指斷開一個(gè)TCP連接時(shí)，需要客戶端和服務(wù)端總共發(fā)送4個(gè)包以確認(rèn)連接的斷開。
由于TCP連接時(shí)全雙工的，因此，每個(gè)方向都必須要單獨(dú)進(jìn)行關(guān)閉，這一原則是當(dāng)一方完成數(shù)據(jù)發(fā)送任務(wù)后，發(fā)送一個(gè)FIN來終止這一方向的連接，收到一個(gè)FIN只是意味著這一方向上沒有數(shù)據(jù)流動(dòng)了，即不會(huì)再收到數(shù)據(jù)了，但是在這個(gè)TCP連接上仍然能夠發(fā)送數(shù)據(jù)，直到這一方向也發(fā)送了FIN。首先進(jìn)行關(guān)閉的一方將執(zhí)行主動(dòng)關(guān)閉，而另一方則執(zhí)行被動(dòng)關(guān)閉，上圖描述的即是如此。 （1）第一次揮手：Client發(fā)送一個(gè)FIN，用來關(guān)閉Client到Server的數(shù)據(jù)傳送，Client進(jìn)入FIN_WAIT_1狀態(tài)。 |
|
|
