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