• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            小角色,大心臟

            C++博客 首頁 新隨筆 聯(lián)系 聚合 管理
              6 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks

            2011年6月21日 #

            某此報(bào)告會上,提到NP問題,不是清楚,現(xiàn)查閱如下:
            1)http://en.wikipedia.org/wiki/NP-hard上的解釋;
            2)弄清楚這幾個概念:計(jì)算復(fù)雜性以及其排序和問題規(guī)約等;
            ##計(jì)算復(fù)雜性
            這是描述一種算法需要多少“時間”的度量。(也有空間復(fù)雜性,但因?yàn)樗鼈兡芟嗷マD(zhuǎn)換,所以通常我們就說時間復(fù)雜性。對于大小為 n 的輸入,我們用含 n 的簡化式子來表達(dá)。(所謂簡化式子,就是忽略系數(shù)、常數(shù),僅保留最“大”的那部分)
            比如找出 n 個數(shù)中最大的一個,很簡單,就是把第一個數(shù)和第二個比,其中大的那個再和第三個比,依次類推,總共要比 n-1 次,我們記作 O(n) (對于 n 可以是很大很大的情況下,-1可以忽略不計(jì)了)。
            再比如從小到大排好的 n 個數(shù),從中找出等于 x 的那個。一種方法是按著順序從頭到尾一個個找,最好情況是第一個就是 x,最壞情況是比較了 n 次直最后一個,因此最壞情況下的計(jì)算復(fù)雜度也是 O(n)。還有一種方法:先取中間那個數(shù)和 x 比較,如偏大則在前一半數(shù)中找,如偏小則在后一半數(shù)中找,每次都是取中間的那個數(shù)進(jìn)行比較,則最壞情況是 lg(n)/lg2。忽略系數(shù)lg2,算法復(fù)雜度是O(lgn)。

            ##計(jì)算復(fù)雜性的排序:
            根據(jù)含 n 的表達(dá)式隨 n 增大的增長速度,可以將它們排序:1 < lg(n) < n < nlg(n) < n^2 < ... < n^k (k是常數(shù))< ... < 2^n。最后這個 2 的 n 次方就是級數(shù)增長了,讀過棋盤上放麥粒故事的人都知道這個增長速度有多快。而之前的那些都是 n 的多項(xiàng)式時間的復(fù)雜度。為什么我們在這里忽略所有的系數(shù)、常數(shù),例如 2*n^3+9*n^2 可以被簡化為 n^3?用集合什么的都能解釋,我忘了精確的說法了。如果你還記得微積分的話就想像一下對 (2*n^3+9*n^2)/(n^3) 求導(dǎo),結(jié)果是0,沒區(qū)別,對不?

            ##P 問題:對一個問題,凡是能找到計(jì)算復(fù)雜度可以表示為多項(xiàng)式的確定算法,這個問題就屬于 P (polynomial) 問題。

            ##NP 問題:
            NP 中的 N 是指非確定的(non-deterministic)算法,這是這樣一種算法:(1)猜一個答案。(2)驗(yàn)證這個答案是否正確。(3)只要存在某次驗(yàn)證,答案是正確的,則該算法得解。
            NP (non-deterministic polynomial)問題就是指,用這樣的非確定的算法,驗(yàn)證步驟(2)有多項(xiàng)式時間的計(jì)算復(fù)雜度的算法。

            ##問題的歸約:
            這……我該用什么術(shù)語來解釋呢?集合?太難說清了……如果你還記得函數(shù)的映射的話就比較容易想象了。
            大致就是這樣:找從問題1的所有輸入到問題2的所有輸入的對應(yīng),如果相應(yīng)的,也能有問題2的所有輸出到問題1的所有輸出的對應(yīng),則若我們找到了問題2的解法,就能通過輸入、輸出的對應(yīng)關(guān)系,得到問題1的解法。由此我們說問題1可歸約到問題2。

            ##NP-Hard:
            有這樣一種問題,所有 NP 問題都可以歸約到這種問題,我們稱之為 NP-hard 問題。

            ##NP完全問題 (NP-Complete):
            如果一個問題既是 NP 問題又是 NP-Hard 問題,則它是 NP-Complete 問題。可滿足性問題就是一個 NP 完全問題,此外著名的給圖染色、哈密爾頓環(huán)、背包、貨郎問題都是 NP 完全問題。

            從直覺上說,P<=NP<=NP-Complete<=NP-Hard,問題的難度遞增。但目前只能證明 P 屬于 NP,究竟 P=NP 還是 P 真包含于 NP 還未知。
            posted @ 2011-06-21 10:05 小角色 閱讀(379) | 評論 (0)編輯 收藏

            2011年6月1日 #

            不止一次,看到很多講技術(shù)的文章里面出現(xiàn)過這個詞語。在WIKI上的解釋如下: 

            In computer science, bleeding edge is a term that refers to technology that is so new (and thus, presumably, not perfected) that the user is required to risk reductions in stability and productivity in order to use it. It also refers to the tendency of the latest technology to be extremely expensive. The term was first coined by Peter Barus, a Superbase programmer.

            在計(jì)算機(jī)領(lǐng)域,Bleeding Edge指一種最新的、因而也并非完美的技術(shù)。使用者為了它的新,就要拿穩(wěn)定性和產(chǎn)量來冒險(xiǎn)。它也指當(dāng)今技術(shù)的每一步發(fā)展都越來越昂貴的趨勢。這個詞的發(fā)明者是一個超級數(shù)據(jù)庫的程序員Peter Barus。

            The term is formed as an allusion to "leading edge" and its synonym cutting edge, but implying a greater degree of risk: the "bleeding edge" is in front of the "cutting edge". A technology may be considered bleeding edge under the following conditions:

            這個詞,可以視作Leading Edge的另一種說法,Cutting Edge的同義詞,但是Bleeding Edge更要隱含一種風(fēng)險(xiǎn)的含義:和Cutting Edge相比,Bleeding Edge更要前衛(wèi)一些。通常,一種技術(shù)如果要被稱作是Bleeding Edge,那么它通常會符合以下幾種特性描述:

            • Lack of consensus — competing ways of doing some new thing exist and no one really knows for certain which way the market is going to go.
            • 沒有公認(rèn)——在達(dá)到同一目標(biāo)的不同的技術(shù)道路之中,沒有人知道,究竟哪一條路會成為市場的最終選擇。
            • Lack of knowledge — organizations are trying to implement a new technology or product that the trade journals have not even started talking about yet, either for or against.
            • 缺乏認(rèn)識——當(dāng)一些機(jī)構(gòu)開始對一項(xiàng)新技術(shù)或者新產(chǎn)品進(jìn)行研發(fā)的時候,行業(yè)媒體甚至還沒有開始對此展開討論,無論是贊成,還是反對。
            • Industry resistance to change — trade journals and industry leaders have spoken against a new technology or product but some organizations are trying to implement it anyway because they are convinced it is technically superior.
            • 遭到產(chǎn)業(yè)抵制——行業(yè)媒體和產(chǎn)業(yè)界已經(jīng)對某項(xiàng)新技術(shù)或者新產(chǎn)品進(jìn)行抨擊,但是一些組織和機(jī)構(gòu)因?yàn)閳?jiān)信其技術(shù)上的優(yōu)越性而繼續(xù)努力完善之。

            The rewards for successful early adoption of new technologies can be great; unfortunately, the penalties for "betting on the wrong horse" or choosing the wrong product are equally large. Whenever an organization decides to take a chance on bleeding edge technology there is a good chance that they will be stuck with a white elephant or worse.

            最早成功采用新技術(shù)所帶來的回報(bào)可能會非常豐厚;然而,如果你下注下錯了,你遭到的懲罰會同樣可觀。因此,當(dāng)一個組織決定采用Bleeding Edge的新技術(shù)時,他們有可能因此而背上沉重的負(fù)擔(dān)甚至更糟。

            Recently however, the term bleeding edge has been increasingly used by the general public to mean "ahead of cutting edge" largely without the negative, risk-associated connotation concurrent with the term's use in more specific fields.

            但是現(xiàn)在,在越來越多的普遍用法中,Bleeding Edge已經(jīng)成為一個只是強(qiáng)調(diào)前衛(wèi)性而沒有風(fēng)險(xiǎn)性的詞語。

            An apt quotation concerning this issue is:"But when you're living on the bleeding edge, you should not be surprised when you do, infact, bleed."

            一個引用環(huán)境是:“當(dāng)你選擇了Bleeding Edge的技術(shù)之后,你就不應(yīng)該為此付出的代價(jià)而感到震驚。”

             

            Bleeding

            posted @ 2011-06-01 19:26 小角色 閱讀(266) | 評論 (0)編輯 收藏

            2011年5月28日 #

            今天學(xué)生問我,class 和 struct 到底有什么區(qū)別?我說:“在C++中,沒有什么區(qū)別”,課下查閱一番,總結(jié)入下

            1)在Cstruct是用來封裝數(shù)據(jù)的,其中不能夠有函數(shù)成員,變量默認(rèn)的存取權(quán)限是public的;

            2)而在C++中集成了在C中的用法并做出改進(jìn),那就是允許struct中有成員函數(shù),這純粹是為了和C兼容,因此如果不需要和C兼容或傳遞參數(shù)給C,建議在C++中不用struct

            而實(shí)際中,大多數(shù)程序員習(xí)慣用struct定義只含數(shù)據(jù)成員的結(jié)構(gòu),而用class定義既含數(shù)據(jù)成員也汗函數(shù)成員的結(jié)構(gòu);

            3)在C++中兩者有微小的用法差異:一是class中成員默認(rèn)的存取權(quán)限是private的,而struct中成員默認(rèn)是public的;二是在用模板的時候只能寫成template <class Type>template <typename Type>,而不能寫成<struct Type>

            4)另外,可以這樣說不管定義在基類還是派生類,classdata member 和 非virtual function的存取效率和struct是一樣的(或說如果沒有多態(tài)和虛擬繼承,二者存取效率相同);
            PS:如有不恰當(dāng)之處,望請指教!

            posted @ 2011-05-28 10:06 小角色 閱讀(276) | 評論 (0)編輯 收藏

            2011年5月20日 #

            哎,墮落了,好幾天不寫代碼了;最近Lonnie Heinke(C++外教)給學(xué)生布置了幾個程序:一個鏈表的,一個STL的。得抽時間搞一搞了。。。。
            posted @ 2011-05-20 21:43 小角色 閱讀(233) | 評論 (0)編輯 收藏

            2011年4月16日 #

            作大二《C++高級程序設(shè)計(jì)》助教已有7周,遇到很多學(xué)生提出來的問題,總的說來都屬于C++基礎(chǔ)問題。然而,由于才疏學(xué)淺,很多次被學(xué)生問懵了,為了面子,不得不私下惡補(bǔ)。Always try to see the half glass full!
            惡補(bǔ)的過程中,總結(jié)了一些問題,本著交流與分享的出發(fā)點(diǎn),偶會在這里不定期更新,希望對C++初學(xué)者有所幫助!也請指出偶的錯誤之處!
            PS:下面提到的觀點(diǎn)并非全部屬于自己,很多是來自各技術(shù)論壇大牛之作,在此引用,謝過先


             

            Question:編譯器會自動創(chuàng)建那些成員函數(shù)呢?什么情況下我們不需要自己寫這些函數(shù)呢?(學(xué)生問時,我說了三種,少了assignment operator)
            Answer:constructor(構(gòu)造函數(shù));destructor(析構(gòu)函數(shù));copy constructor(復(fù)制構(gòu)造函數(shù));assignment operator(賦值操作符)
                          以Human為例:
                                 Human();//默認(rèn)構(gòu)造函數(shù)
                                 ~Human();//析構(gòu)函數(shù)
                                 Human(const Human& p);//復(fù)制構(gòu)造函數(shù)
                                 Human & operator = (const Human & lvalue);//賦值操作符函數(shù)
                           學(xué)生又問了既然編譯器給我們自動創(chuàng)建了這些構(gòu)造函數(shù),為什么我們還要重新自己定義呢?
                           暈倒,我問“構(gòu)造函數(shù)的作用是什么呢?” 答曰“初始化數(shù)據(jù)成員(因?yàn)闊o法在類里面給成員變量賦初值)” “僅僅如此嗎,如果需要實(shí)現(xiàn)一些功能呢,要不要在構(gòu)造函數(shù)里寫?回答是肯定的”。至于其他幾個構(gòu)造函數(shù)別有用途,另行討論;
                           學(xué)生沒有示弱的意思,反問道“那什么情況下,我們不需要寫這些函數(shù)呢” 
                            稍稍考慮了一下,“如果沒有寫構(gòu)造函數(shù),編譯器會自動生成一個不帶參數(shù)的構(gòu)造函數(shù)即默認(rèn)構(gòu)造函數(shù),析構(gòu)函數(shù)類似”,暫時敷衍了一下。后來又想,至于復(fù)制構(gòu)造函數(shù)和賦值呢?查了一下才知道:如果我們只用基本數(shù)據(jù)類型,而沒有用指針或者引用作為數(shù)據(jù)成員,此時就不需要自己寫這些函數(shù)。所以一般情況下,我們通常都寫上這幾個構(gòu)造函數(shù)!
            posted @ 2011-04-16 19:00 小角色 閱讀(335) | 評論 (0)編輯 收藏

            2011年4月12日 #

            • 研一下學(xué)期要搞點(diǎn)東西,用到C++和linux,順便兼職C++TA,知識匱乏,前來充電;
            • 希望多動腦,多動手,分享資源,共同學(xué)習(xí),提高效率;

            posted @ 2011-04-12 23:00 小角色 閱讀(163) | 評論 (0)編輯 收藏

            僅列出標(biāo)題  
            久久电影网2021| 综合久久国产九一剧情麻豆| 国产精品久久久久久福利69堂| 精品免费久久久久久久| 久久99中文字幕久久| 色婷婷久久久SWAG精品| 久久国产精品99精品国产| 亚洲国产精品久久久久久| 久久只有这里有精品4| 久久久一本精品99久久精品88| 国产成人综合久久精品尤物| 国产成人精品三上悠亚久久| 青青青国产精品国产精品久久久久 | 波多野结衣久久一区二区| 久久66热人妻偷产精品9| 久久久久久青草大香综合精品| 色欲久久久天天天综合网精品| 国产精品久久久99| 久久久久久无码Av成人影院| 亚洲精品综合久久| 久久精品国产色蜜蜜麻豆| 丰满少妇高潮惨叫久久久| 久久综合鬼色88久久精品综合自在自线噜噜 | 久久婷婷五月综合97色一本一本| 欧美色综合久久久久久| 91久久精品电影| 久久国产精品久久国产精品| 久久国产亚洲精品| 中文字幕无码av激情不卡久久| 久久综合九色综合久99| 2022年国产精品久久久久| 狠狠综合久久AV一区二区三区| 亚洲综合久久夜AV | 欧美一级久久久久久久大| 久久成人国产精品一区二区| 日韩一区二区久久久久久| 欧美久久综合性欧美| 999久久久免费国产精品播放| 久久精品九九亚洲精品天堂| 99久久精品日本一区二区免费 | 久久久久AV综合网成人 |