• <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)告會(huì)上,提到NP問題,不是清楚,現(xiàn)查閱如下:
            1)http://en.wikipedia.org/wiki/NP-hard上的解釋;
            2)弄清楚這幾個(gè)概念:計(jì)算復(fù)雜性以及其排序和問題規(guī)約等;
            ##計(jì)算復(fù)雜性
            這是描述一種算法需要多少“時(shí)間”的度量。(也有空間復(fù)雜性,但因?yàn)樗鼈兡芟嗷マD(zhuǎn)換,所以通常我們就說時(shí)間復(fù)雜性。對于大小為 n 的輸入,我們用含 n 的簡化式子來表達(dá)。(所謂簡化式子,就是忽略系數(shù)、常數(shù),僅保留最“大”的那部分)
            比如找出 n 個(gè)數(shù)中最大的一個(gè),很簡單,就是把第一個(gè)數(shù)和第二個(gè)比,其中大的那個(gè)再和第三個(gè)比,依次類推,總共要比 n-1 次,我們記作 O(n) (對于 n 可以是很大很大的情況下,-1可以忽略不計(jì)了)。
            再比如從小到大排好的 n 個(gè)數(shù),從中找出等于 x 的那個(gè)。一種方法是按著順序從頭到尾一個(gè)個(gè)找,最好情況是第一個(gè)就是 x,最壞情況是比較了 n 次直最后一個(gè),因此最壞情況下的計(jì)算復(fù)雜度也是 O(n)。還有一種方法:先取中間那個(gè)數(shù)和 x 比較,如偏大則在前一半數(shù)中找,如偏小則在后一半數(shù)中找,每次都是取中間的那個(gè)數(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。最后這個(gè) 2 的 n 次方就是級數(shù)增長了,讀過棋盤上放麥粒故事的人都知道這個(gè)增長速度有多快。而之前的那些都是 n 的多項(xiàng)式時(shí)間的復(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 問題:對一個(gè)問題,凡是能找到計(jì)算復(fù)雜度可以表示為多項(xiàng)式的確定算法,這個(gè)問題就屬于 P (polynomial) 問題。

            ##NP 問題:
            NP 中的 N 是指非確定的(non-deterministic)算法,這是這樣一種算法:(1)猜一個(gè)答案。(2)驗(yàn)證這個(gè)答案是否正確。(3)只要存在某次驗(yàn)證,答案是正確的,則該算法得解。
            NP (non-deterministic polynomial)問題就是指,用這樣的非確定的算法,驗(yàn)證步驟(2)有多項(xiàng)式時(shí)間的計(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):
            如果一個(gè)問題既是 NP 問題又是 NP-Hard 問題,則它是 NP-Complete 問題。可滿足性問題就是一個(gè) NP 完全問題,此外著名的給圖染色、哈密爾頓環(huán)、背包、貨郎問題都是 NP 完全問題。

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

            2011年6月1日 #

            不止一次,看到很多講技術(shù)的文章里面出現(xiàn)過這個(gè)詞語。在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ā)展都越來越昂貴的趨勢。這個(gè)詞的發(fā)明者是一個(gè)超級數(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:

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

            • 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ù)道路之中,沒有人知道,究竟哪一條路會(huì)成為市場的最終選擇。
            • 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)識(shí)——當(dāng)一些機(jī)構(gòu)開始對一項(xiàng)新技術(shù)或者新產(chǎn)品進(jìn)行研發(fā)的時(shí)候,行業(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)可能會(huì)非常豐厚;然而,如果你下注下錯(cuò)了,你遭到的懲罰會(huì)同樣可觀。因此,當(dāng)一個(gè)組織決定采用Bleeding Edge的新技術(shù)時(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)成為一個(gè)只是強(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."

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

             

            Bleeding

            posted @ 2011-06-01 19:26 小角色 閱讀(257) | 評論 (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的;二是在用模板的時(shí)候只能寫成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 小角色 閱讀(270) | 評論 (0)編輯 收藏

            2011年5月20日 #

            哎,墮落了,好幾天不寫代碼了;最近Lonnie Heinke(C++外教)給學(xué)生布置了幾個(gè)程序:一個(gè)鏈表的,一個(gè)STL的。得抽時(shí)間搞一搞了。。。。
            posted @ 2011-05-20 21:43 小角色 閱讀(224) | 評論 (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),偶會(huì)在這里不定期更新,希望對C++初學(xué)者有所幫助!也請指出偶的錯(cuò)誤之處!
            PS:下面提到的觀點(diǎn)并非全部屬于自己,很多是來自各技術(shù)論壇大牛之作,在此引用,謝過先


             

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

            2011年4月12日 #

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

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

            僅列出標(biāo)題  
            99久久综合狠狠综合久久止| 国产精品99久久不卡| 亚洲精品久久久www| 亚洲人成无码网站久久99热国产| 久久久久亚洲AV成人网人人网站| 无码超乳爆乳中文字幕久久| 久久久国产精品网站| 久久精品人妻中文系列| 久久香蕉国产线看观看99 | 无码人妻久久一区二区三区蜜桃 | 亚洲国产精品无码久久久蜜芽| 午夜精品久久久久久影视riav| 蜜臀av性久久久久蜜臀aⅴ| 久久精品亚洲欧美日韩久久| 午夜天堂精品久久久久| 久久精品国产一区二区三区不卡| 久久精品人人做人人爽电影| 久久久久久毛片免费看| 久久国产高清字幕中文| 久久精品国产亚洲av麻豆图片| 久久99精品久久久久久水蜜桃| 久久免费的精品国产V∧| 久久精品无码一区二区三区免费| a级成人毛片久久| 囯产极品美女高潮无套久久久| 日韩欧美亚洲国产精品字幕久久久| 精品999久久久久久中文字幕| 色8久久人人97超碰香蕉987| 欧洲国产伦久久久久久久| 99精品伊人久久久大香线蕉| 97久久精品无码一区二区天美| 久久久久人妻一区二区三区| 日韩亚洲国产综合久久久| 久久久WWW免费人成精品| 一本伊大人香蕉久久网手机| 成人综合伊人五月婷久久| 久久精品aⅴ无码中文字字幕重口 久久精品a亚洲国产v高清不卡 | 日韩美女18网站久久精品| 久久婷婷色综合一区二区| 久久精品无码一区二区三区免费 | 成人午夜精品无码区久久|