前言 Rxjava由于其基于事件流的鏈?zhǔn)秸{(diào)用、邏輯簡潔 & 使用簡單的特點(diǎn)，深受各大 Android開發(fā)者的歡迎。本文主要： 面向 剛接觸Rxjava的初學(xué)者 提供了一份 清...
發(fā)簡信
IP屬地：遼寧
-
Carson帶你學(xué)Android：這是一篇清晰易懂的Rxjava入門教程 -
你已經(jīng)理解了O(n)的數(shù)學(xué)含義。
數(shù)學(xué)上要求存在N可以使T(N)<=f(N)，所以f(N)才能成為T(N)的上界。
所以T(n)=n+29嚴(yán)格來說時(shí)間復(fù)雜度是O(n)=n+29。
但是，時(shí)間復(fù)雜度根據(jù)這個(gè)數(shù)學(xué)含義做了延伸。
表示隨著 輸入大小n 的增大，算法執(zhí)行需要的時(shí)間的增長速度的量級。
既然是為了形容“增速”，+29 這種常數(shù)項(xiàng)就對時(shí)間復(fù)雜度沒有影響，可以忽略。
既然是為了形容“量級”，就不需要非常準(zhǔn)確，函數(shù)的階數(shù)對增長速度起了最主要的作用，所以也忽略 2n 中的 2 這種常數(shù)。
最后得出時(shí)間復(fù)雜度就是O(n)。（數(shù)據(jù)結(jié)構(gòu)）十分鐘搞定時(shí)間復(fù)雜度（算法的時(shí)間復(fù)雜度）
我們假設(shè)計(jì)算機(jī)運(yùn)行一行基礎(chǔ)代碼需要執(zhí)行一次運(yùn)算。 那么上面這個(gè)方法需要執(zhí)行 2 次運(yùn)算 這個(gè)方法需要 (n + 1 + n + 1) = 2n + 2 次運(yùn)算。 我們把 算...
-
是的, 就是這個(gè)意思。
直接寫是根據(jù)定義來的：
定義：存在常數(shù) c 和函數(shù) f(N)，使得當(dāng) N >= c 時(shí) T(N) <= f(N)，表示為 T(n) = O(f(n)) 。（數(shù)據(jù)結(jié)構(gòu)）十分鐘搞定時(shí)間復(fù)雜度（算法的時(shí)間復(fù)雜度）
我們假設(shè)計(jì)算機(jī)運(yùn)行一行基礎(chǔ)代碼需要執(zhí)行一次運(yùn)算。 那么上面這個(gè)方法需要執(zhí)行 2 次運(yùn)算 這個(gè)方法需要 (n + 1 + n + 1) = 2n + 2 次運(yùn)算。 我們把 算...
-
你的理解是對的, f(n)=2n 也可以。
文章舉例只是為了說明O(n)的數(shù)學(xué)含義。
正如文中所講：
從數(shù)學(xué)上看如果 T(n) = n + 2（上文中是T(n) = n^2），那么 T(n) = O(n + 3) ，T(n) = O(2n)， T(n) = O(n^2)都是成立的，但是因?yàn)榈谝粋€(gè) f(n) 的增長速度與 T(n) 是最接近的，所以第一個(gè)是更好的選擇，所以我們說這個(gè)算法的復(fù)雜度是 O(n + 3) 。但是由于時(shí)間復(fù)雜度是為了衡量量級，并不需要精確，所以我們舍棄對函數(shù)增長沒有影響的常數(shù)，認(rèn)為T(n) = n + 2的時(shí)間復(fù)雜度是 O(n)。（數(shù)據(jù)結(jié)構(gòu)）十分鐘搞定時(shí)間復(fù)雜度（算法的時(shí)間復(fù)雜度）
我們假設(shè)計(jì)算機(jī)運(yùn)行一行基礎(chǔ)代碼需要執(zhí)行一次運(yùn)算。 那么上面這個(gè)方法需要執(zhí)行 2 次運(yùn)算 這個(gè)方法需要 (n + 1 + n + 1) = 2n + 2 次運(yùn)算。 我們把 算...
-
@飛哥白尼 可以參考其他人的評論, 有說到這個(gè)問題的, 希望可以幫到你
（數(shù)據(jù)結(jié)構(gòu)）十分鐘搞定時(shí)間復(fù)雜度（算法的時(shí)間復(fù)雜度）
我們假設(shè)計(jì)算機(jī)運(yùn)行一行基礎(chǔ)代碼需要執(zhí)行一次運(yùn)算。 那么上面這個(gè)方法需要執(zhí)行 2 次運(yùn)算 這個(gè)方法需要 (n + 1 + n + 1) = 2n + 2 次運(yùn)算。 我們把 算...
-
大寫的N，代表某個(gè)特定數(shù)值。
小寫的n，是函數(shù)的變量。（數(shù)據(jù)結(jié)構(gòu)）十分鐘搞定時(shí)間復(fù)雜度（算法的時(shí)間復(fù)雜度）
我們假設(shè)計(jì)算機(jī)運(yùn)行一行基礎(chǔ)代碼需要執(zhí)行一次運(yùn)算。 那么上面這個(gè)方法需要執(zhí)行 2 次運(yùn)算 這個(gè)方法需要 (n + 1 + n + 1) = 2n + 2 次運(yùn)算。 我們把 算...
-
有道理。
應(yīng)該說：
定義： 存在常數(shù) c 和函數(shù) f(N)，使得當(dāng) N >= c 時(shí) T(N) <= f(N)，表示為 T(n) = O(f(n)) 。（數(shù)據(jù)結(jié)構(gòu)）十分鐘搞定時(shí)間復(fù)雜度（算法的時(shí)間復(fù)雜度）
我們假設(shè)計(jì)算機(jī)運(yùn)行一行基礎(chǔ)代碼需要執(zhí)行一次運(yùn)算。 那么上面這個(gè)方法需要執(zhí)行 2 次運(yùn)算 這個(gè)方法需要 (n + 1 + n + 1) = 2n + 2 次運(yùn)算。 我們把 算...
-
評論里有更加詳盡的解析，你可以看看
（數(shù)據(jù)結(jié)構(gòu)）十分鐘搞定時(shí)間復(fù)雜度（算法的時(shí)間復(fù)雜度）
我們假設(shè)計(jì)算機(jī)運(yùn)行一行基礎(chǔ)代碼需要執(zhí)行一次運(yùn)算。 那么上面這個(gè)方法需要執(zhí)行 2 次運(yùn)算 這個(gè)方法需要 (n + 1 + n + 1) = 2n + 2 次運(yùn)算。 我們把 算...
-
時(shí)間復(fù)雜度分析的基本策略是：從內(nèi)向外分析，從最深層開始分析。如果遇到函數(shù)調(diào)用，要深入函數(shù)進(jìn)行分析。
再次進(jìn)階里的return，是進(jìn)行了兩次函數(shù)調(diào)用之后才返回的。
時(shí)間復(fù)雜度的計(jì)算是不能忽略函數(shù)調(diào)用的。（數(shù)據(jù)結(jié)構(gòu)）十分鐘搞定時(shí)間復(fù)雜度（算法的時(shí)間復(fù)雜度）
我們假設(shè)計(jì)算機(jī)運(yùn)行一行基礎(chǔ)代碼需要執(zhí)行一次運(yùn)算。 那么上面這個(gè)方法需要執(zhí)行 2 次運(yùn)算 這個(gè)方法需要 (n + 1 + n + 1) = 2n + 2 次運(yùn)算。 我們把 算...
-
再次進(jìn)階的理解不必強(qiáng)求
需要的更多是數(shù)學(xué)能力（數(shù)據(jù)結(jié)構(gòu)）十分鐘搞定時(shí)間復(fù)雜度（算法的時(shí)間復(fù)雜度）
我們假設(shè)計(jì)算機(jī)運(yùn)行一行基礎(chǔ)代碼需要執(zhí)行一次運(yùn)算。 那么上面這個(gè)方法需要執(zhí)行 2 次運(yùn)算 這個(gè)方法需要 (n + 1 + n + 1) = 2n + 2 次運(yùn)算。 我們把 算...
-
因?yàn)?常數(shù)因子c 對函數(shù)的增長速度的影響并沒有 函數(shù)的階次 顯著。
時(shí)間復(fù)雜度只是一種描述，并不需要非常嚴(yán)謹(jǐn)，所以忽略這個(gè)影響比較小的因素。（數(shù)據(jù)結(jié)構(gòu)）十分鐘搞定時(shí)間復(fù)雜度（算法的時(shí)間復(fù)雜度）
我們假設(shè)計(jì)算機(jī)運(yùn)行一行基礎(chǔ)代碼需要執(zhí)行一次運(yùn)算。 那么上面這個(gè)方法需要執(zhí)行 2 次運(yùn)算 這個(gè)方法需要 (n + 1 + n + 1) = 2n + 2 次運(yùn)算。 我們把 算...
-
你有疑問是對的。
這里嚴(yán)格來說確實(shí)不準(zhǔn)確，
for(int i=0;i<n;i++) 其實(shí)是
int i=0;
while(i<n){
......
i++;
}
運(yùn)算次數(shù)其實(shí)不少，但是時(shí)間復(fù)雜度是衡量程序運(yùn)行時(shí)間隨輸入大小變化的量級，所以不需要太準(zhǔn)確。
就好像我們說這輛車的車速很快，超過120。
于是我們用 超過120 這個(gè)量級表示 這個(gè)車的速度。
這種時(shí)候，具體是121,122,125并不重要。
用 A 來表示 B，從而可以忽略不重要的東西，把精力集中在更加重要的地方。
時(shí)間復(fù)雜度就是這樣，通俗地理解就是用 一個(gè)函數(shù)（隨x的增長速度） 來表示一段程序的運(yùn)行時(shí)間隨輸入大小變化的速度。（數(shù)據(jù)結(jié)構(gòu)）十分鐘搞定時(shí)間復(fù)雜度（算法的時(shí)間復(fù)雜度）
我們假設(shè)計(jì)算機(jī)運(yùn)行一行基礎(chǔ)代碼需要執(zhí)行一次運(yùn)算。 那么上面這個(gè)方法需要執(zhí)行 2 次運(yùn)算 這個(gè)方法需要 (n + 1 + n + 1) = 2n + 2 次運(yùn)算。 我們把 算...