很可惜 T 。T 您現(xiàn)在還不是作者身份,不能自主發(fā)稿哦~
如有投稿需求,請把文章發(fā)送到郵箱tougao@appcpx.com,一經(jīng)錄用會有專人和您聯(lián)系
咨詢?nèi)绾纬蔀榇河鹱髡哒埪?lián)系:鳥哥筆記小羽毛(ngbjxym)
為了計(jì)算時(shí)間復(fù)雜度,我們通常會估計(jì)算法的操作單元數(shù)量,每個(gè)單元運(yùn)行的時(shí)間都是相同的。因此,總運(yùn)行時(shí)間和算法的操作單元數(shù)量最多相差一個(gè)常量系數(shù)。
相同大小的不同輸入值仍可能造成算法的運(yùn)行時(shí)間不同,因此我們通常使用算法的最壞情況復(fù)雜度,記為T(n),定義為任何大小的輸入n所需的最大運(yùn)行時(shí)間。另一種較少使用的方法是平均情況復(fù)雜度,通常有特別指定才會使用。時(shí)間復(fù)雜度可以用函數(shù)T(n) 的自然特性加以分類,舉例來說,有著T(n) =O(n) 的算法被稱作“線性時(shí)間算法”;而T(n) =O(M^n) 和M= O(T(n)) ,其中M≥n> 1 的算法被稱作“指數(shù)時(shí)間算法”。
一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例,哪個(gè)算法中語句執(zhí)行次數(shù)多,它花費(fèi)的時(shí)間就多。一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度。記為T(n)。
一般情況下,算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù),用T(n)表示,若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí),T(n)/f (n)的極限值為不等于零的常數(shù),則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度,簡稱時(shí)間復(fù)雜度。
在各種不同算法中,若算法中語句執(zhí)行次數(shù)為一個(gè)常數(shù),則時(shí)間復(fù)雜度為O(1),另外,在時(shí)間頻度不相同時(shí),時(shí)間復(fù)雜度有可能相同,如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同,但時(shí)間復(fù)雜度相同,都為O(n2)。
時(shí)間頻度
一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間,從理論上是不能算出來的,必須上機(jī)運(yùn)行測試才能知道。但我們不可能也沒有必要對每個(gè)算法都上機(jī)測試,只需知道哪個(gè)算法花費(fèi)的時(shí)間多,哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例,哪個(gè)算法中語句執(zhí)行次數(shù)多,它花費(fèi)的時(shí)間就多。一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度。記為T(n)。
1.常數(shù)階O(1)
無論代碼執(zhí)行了多少行,只要是沒有循環(huán)等復(fù)雜結(jié)構(gòu),那這個(gè)代碼的時(shí)間復(fù)雜度就都是O(1)如:
int i = 1;int j = 2;
++i;
j++;int m = i + j;
上述代碼在執(zhí)行的時(shí)候,它消耗的時(shí)候并不隨著某個(gè)變量的增長而增長,那么無論這類代碼有多長,即使有幾萬幾十萬行,都可以用O(1)來表示它的時(shí)間復(fù)雜度。
2.對數(shù)階O(logN)
int i = 1;while(i
{
i = i * 2;
}
從上面代碼可以看到,在while循環(huán)里面,每次都將 i 乘以 2,乘完之后,i 距離 n 就越來越近了。我們試著求解一下,假設(shè)循環(huán)x次之后,i 就大于n了,此時(shí)這個(gè)循環(huán)就退出了,也就是說 2 的 x 次方等于 n,那么 x = log2^n
也就是說當(dāng)循環(huán) log2^n 次以后,這個(gè)代碼就結(jié)束了。因此這個(gè)代碼的時(shí)間復(fù)雜度為:O(logn)
3.線性階O(n)
for(i=1; i<=n; ++i)
{ j = i;
j++;
}
這段代碼,for循環(huán)里面的代碼會執(zhí)行n遍,因此它消耗的時(shí)間是隨著n的變化而變化的,因此這類代碼都可以用O(n)來表示它的時(shí)間復(fù)雜度。
4.線性對數(shù)階O(nlogN)
線性對數(shù)階O(nlogN) 其實(shí)非常容易理解,將時(shí)間復(fù)雜度為O(logn)的代碼循環(huán)N遍的話,那么它的時(shí)間復(fù)雜度就是 n * O(logN),也就是了O(nlogN)。
就拿上面的代碼加一點(diǎn)修改來舉例:
for(m=1; m
i = 1;
while(i{
i = i * 2;
}}
5.平方階O(n2)
平方階O(n2) 就更容易理解了,如果把 O(n) 的代碼再嵌套循環(huán)一遍,它的時(shí)間復(fù)雜度就是 O(n2) 了。
舉例:
for(x=1; i<=n; x++){
for(i=1; i<=n; i++)
{
j = i;
j++;
}}
小結(jié):O(1) < O(logn) < O(n) < O(nlogn) < O(n^2)
本文為作者獨(dú)立觀點(diǎn),不代表鳥哥筆記立場,未經(jīng)允許不得轉(zhuǎn)載。
《鳥哥筆記版權(quán)及免責(zé)申明》 如對文章、圖片、字體等版權(quán)有疑問,請點(diǎn)擊 反饋舉報(bào)
我們致力于提供一個(gè)高質(zhì)量內(nèi)容的交流平臺。為落實(shí)國家互聯(lián)網(wǎng)信息辦公室“依法管網(wǎng)、依法辦網(wǎng)、依法上網(wǎng)”的要求,為完善跟帖評論自律管理,為了保護(hù)用戶創(chuàng)造的內(nèi)容、維護(hù)開放、真實(shí)、專業(yè)的平臺氛圍,我們團(tuán)隊(duì)將依據(jù)本公約中的條款對注冊用戶和發(fā)布在本平臺的內(nèi)容進(jìn)行管理。平臺鼓勵用戶創(chuàng)作、發(fā)布優(yōu)質(zhì)內(nèi)容,同時(shí)也將采取必要措施管理違法、侵權(quán)或有其他不良影響的網(wǎng)絡(luò)信息。
一、根據(jù)《網(wǎng)絡(luò)信息內(nèi)容生態(tài)治理規(guī)定》《中華人民共和國未成年人保護(hù)法》等法律法規(guī),對以下違法、不良信息或存在危害的行為進(jìn)行處理。
1. 違反法律法規(guī)的信息,主要表現(xiàn)為:
1)反對憲法所確定的基本原則;
2)危害國家安全,泄露國家秘密,顛覆國家政權(quán),破壞國家統(tǒng)一,損害國家榮譽(yù)和利益;
3)侮辱、濫用英烈形象,歪曲、丑化、褻瀆、否定英雄烈士事跡和精神,以侮辱、誹謗或者其他方式侵害英雄烈士的姓名、肖像、名譽(yù)、榮譽(yù);
4)宣揚(yáng)恐怖主義、極端主義或者煽動實(shí)施恐怖活動、極端主義活動;
5)煽動民族仇恨、民族歧視,破壞民族團(tuán)結(jié);
6)破壞國家宗教政策,宣揚(yáng)邪教和封建迷信;
7)散布謠言,擾亂社會秩序,破壞社會穩(wěn)定;
8)宣揚(yáng)淫穢、色情、賭博、暴力、兇殺、恐怖或者教唆犯罪;
9)煽動非法集會、結(jié)社、游行、示威、聚眾擾亂社會秩序;
10)侮辱或者誹謗他人,侵害他人名譽(yù)、隱私和其他合法權(quán)益;
11)通過網(wǎng)絡(luò)以文字、圖片、音視頻等形式,對未成年人實(shí)施侮辱、誹謗、威脅或者惡意損害未成年人形象進(jìn)行網(wǎng)絡(luò)欺凌的;
12)危害未成年人身心健康的;
13)含有法律、行政法規(guī)禁止的其他內(nèi)容;
2. 不友善:不尊重用戶及其所貢獻(xiàn)內(nèi)容的信息或行為。主要表現(xiàn)為:
1)輕蔑:貶低、輕視他人及其勞動成果;
2)誹謗:捏造、散布虛假事實(shí),損害他人名譽(yù);
3)嘲諷:以比喻、夸張、侮辱性的手法對他人或其行為進(jìn)行揭露或描述,以此來激怒他人;
4)挑釁:以不友好的方式激怒他人,意圖使對方對自己的言論作出回應(yīng),蓄意制造事端;
5)羞辱:貶低他人的能力、行為、生理或身份特征,讓對方難堪;
6)謾罵:以不文明的語言對他人進(jìn)行負(fù)面評價(jià);
7)歧視:煽動人群歧視、地域歧視等,針對他人的民族、種族、宗教、性取向、性別、年齡、地域、生理特征等身份或者歸類的攻擊;
8)威脅:許諾以不良的后果來迫使他人服從自己的意志;
3. 發(fā)布垃圾廣告信息:以推廣曝光為目的,發(fā)布影響用戶體驗(yàn)、擾亂本網(wǎng)站秩序的內(nèi)容,或進(jìn)行相關(guān)行為。主要表現(xiàn)為:
1)多次發(fā)布包含售賣產(chǎn)品、提供服務(wù)、宣傳推廣內(nèi)容的垃圾廣告。包括但不限于以下幾種形式:
2)單個(gè)帳號多次發(fā)布包含垃圾廣告的內(nèi)容;
3)多個(gè)廣告帳號互相配合發(fā)布、傳播包含垃圾廣告的內(nèi)容;
4)多次發(fā)布包含欺騙性外鏈的內(nèi)容,如未注明的淘寶客鏈接、跳轉(zhuǎn)網(wǎng)站等,誘騙用戶點(diǎn)擊鏈接
5)發(fā)布大量包含推廣鏈接、產(chǎn)品、品牌等內(nèi)容獲取搜索引擎中的不正當(dāng)曝光;
6)購買或出售帳號之間虛假地互動,發(fā)布干擾網(wǎng)站秩序的推廣內(nèi)容及相關(guān)交易。
7)發(fā)布包含欺騙性的惡意營銷內(nèi)容,如通過偽造經(jīng)歷、冒充他人等方式進(jìn)行惡意營銷;
8)使用特殊符號、圖片等方式規(guī)避垃圾廣告內(nèi)容審核的廣告內(nèi)容。
4. 色情低俗信息,主要表現(xiàn)為:
1)包含自己或他人性經(jīng)驗(yàn)的細(xì)節(jié)描述或露骨的感受描述;
2)涉及色情段子、兩性笑話的低俗內(nèi)容;
3)配圖、頭圖中包含庸俗或挑逗性圖片的內(nèi)容;
4)帶有性暗示、性挑逗等易使人產(chǎn)生性聯(lián)想;
5)展現(xiàn)血腥、驚悚、殘忍等致人身心不適;
6)炒作緋聞、丑聞、劣跡等;
7)宣揚(yáng)低俗、庸俗、媚俗內(nèi)容。
5. 不實(shí)信息,主要表現(xiàn)為:
1)可能存在事實(shí)性錯誤或者造謠等內(nèi)容;
2)存在事實(shí)夸大、偽造虛假經(jīng)歷等誤導(dǎo)他人的內(nèi)容;
3)偽造身份、冒充他人,通過頭像、用戶名等個(gè)人信息暗示自己具有特定身份,或與特定機(jī)構(gòu)或個(gè)人存在關(guān)聯(lián)。
6. 傳播封建迷信,主要表現(xiàn)為:
1)找人算命、測字、占卜、解夢、化解厄運(yùn)、使用迷信方式治?。?br /> 2)求推薦算命看相大師;
3)針對具體風(fēng)水等問題進(jìn)行求助或咨詢;
4)問自己或他人的八字、六爻、星盤、手相、面相、五行缺失,包括通過占卜方法問婚姻、前程、運(yùn)勢,東西寵物丟了能不能找回、取名改名等;
7. 文章標(biāo)題黨,主要表現(xiàn)為:
1)以各種夸張、獵奇、不合常理的表現(xiàn)手法等行為來誘導(dǎo)用戶;
2)內(nèi)容與標(biāo)題之間存在嚴(yán)重不實(shí)或者原意扭曲;
3)使用夸張標(biāo)題,內(nèi)容與標(biāo)題嚴(yán)重不符的。
8.「飯圈」亂象行為,主要表現(xiàn)為:
1)誘導(dǎo)未成年人應(yīng)援集資、高額消費(fèi)、投票打榜
2)粉絲互撕謾罵、拉踩引戰(zhàn)、造謠攻擊、人肉搜索、侵犯隱私
3)鼓動「飯圈」粉絲攀比炫富、奢靡享樂等行為
4)以號召粉絲、雇用網(wǎng)絡(luò)水軍、「養(yǎng)號」形式刷量控評等行為
5)通過「蹭熱點(diǎn)」、制造話題等形式干擾輿論,影響傳播秩序
9. 其他危害行為或內(nèi)容,主要表現(xiàn)為:
1)可能引發(fā)未成年人模仿不安全行為和違反社會公德行為、誘導(dǎo)未成年人不良嗜好影響未成年人身心健康的;
2)不當(dāng)評述自然災(zāi)害、重大事故等災(zāi)難的;
3)美化、粉飾侵略戰(zhàn)爭行為的;
4)法律、行政法規(guī)禁止,或可能對網(wǎng)絡(luò)生態(tài)造成不良影響的其他內(nèi)容。
二、違規(guī)處罰
本網(wǎng)站通過主動發(fā)現(xiàn)和接受用戶舉報(bào)兩種方式收集違規(guī)行為信息。所有有意的降低內(nèi)容質(zhì)量、傷害平臺氛圍及欺凌未成年人或危害未成年人身心健康的行為都是不能容忍的。
當(dāng)一個(gè)用戶發(fā)布違規(guī)內(nèi)容時(shí),本網(wǎng)站將依據(jù)相關(guān)用戶違規(guī)情節(jié)嚴(yán)重程度,對帳號進(jìn)行禁言 1 天、7 天、15 天直至永久禁言或封停賬號的處罰。當(dāng)涉及欺凌未成年人、危害未成年人身心健康、通過作弊手段注冊、使用帳號,或者濫用多個(gè)帳號發(fā)布違規(guī)內(nèi)容時(shí),本網(wǎng)站將加重處罰。
三、申訴
隨著平臺管理經(jīng)驗(yàn)的不斷豐富,本網(wǎng)站出于維護(hù)本網(wǎng)站氛圍和秩序的目的,將不斷完善本公約。
如果本網(wǎng)站用戶對本網(wǎng)站基于本公約規(guī)定做出的處理有異議,可以通過「建議反饋」功能向本網(wǎng)站進(jìn)行反饋。
(規(guī)則的最終解釋權(quán)歸屬本網(wǎng)站所有)