小角色，大心臟

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

##計算復(fù)雜性的排序：
根據(jù)含 n 的表達式隨 n 增大的增長速度，可以將它們排序：1 < lg(n) < n < nlg(n) < n^2 < ... < n^k (k是常數(shù)）< ... < 2^n。最后這個 2 的 n 次方就是級數(shù)增長了，讀過棋盤上放麥粒故事的人都知道這個增長速度有多快。而之前的那些都是 n 的多項式時間的復(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 問題：對一個問題，凡是能找到計算復(fù)雜度可以表示為多項式的確定算法，這個問題就屬于 P (polynomial) 問題。

##NP 問題：
NP 中的 N 是指非確定的(non-deterministic）算法，這是這樣一種算法：（1）猜一個答案。（2）驗證這個答案是否正確。（3）只要存在某次驗證，答案是正確的，則該算法得解。
NP (non-deterministic polynomial)問題就是指，用這樣的非確定的算法，驗證步驟（2）有多項式時間的計算復(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 還未知。

不止一次，看到很多講技術(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.

在計算機領(lǐng)域，Bleeding Edge指一種最新的、因而也并非完美的技術(shù)。使用者為了它的新，就要拿穩(wěn)定性和產(chǎ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)險的含義：和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.
• 沒有公認——在達到同一目標(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.
• 缺乏認識——當(dāng)一些機構(gòu)開始對一項新技術(shù)或者新產(chǎ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)對某項新技術(shù)或者新產(chǎn)品進行抨擊，但是一些組織和機構(gòu)因為堅信其技術(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ù)所帶來的回報可能會非常豐厚；然而，如果你下注下錯了，你遭到的懲罰會同樣可觀。因此，當(dāng)一個組織決定采用Bleeding Edge的新技術(shù)時，他們有可能因此而背上沉重的負擔(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)成為一個只是強調(diào)前衛(wèi)性而沒有風(fēng)險性的詞語。

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)該為此付出的代價而感到震驚。”

 

Bleeding

作大二《C++高級程序設(shè)計》助教已有7周，遇到很多學(xué)生提出來的問題，總的說來都屬于C++基礎(chǔ)問題。然而，由于才疏學(xué)淺，很多次被學(xué)生問懵了，為了面子，不得不私下惡補。Always try to see the half glass full!
惡補的過程中，總結(jié)了一些問題，本著交流與分享的出發(fā)點，偶會在這里不定期更新，希望對C++初學(xué)者有所幫助！也請指出偶的錯誤之處！
PS:下面提到的觀點并非全部屬于自己，很多是來自各技術(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();//默認構(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ù)成員（因為無法在類里面給成員變量賦初值）” “僅僅如此嗎，如果需要實現(xiàn)一些功能呢，要不要在構(gòu)造函數(shù)里寫？回答是肯定的”。至于其他幾個構(gòu)造函數(shù)別有用途，另行討論；
               學(xué)生沒有示弱的意思，反問道“那什么情況下，我們不需要寫這些函數(shù)呢” 
                稍稍考慮了一下，“如果沒有寫構(gòu)造函數(shù)，編譯器會自動生成一個不帶參數(shù)的構(gòu)造函數(shù)即默認構(gòu)造函數(shù)，析構(gòu)函數(shù)類似”，暫時敷衍了一下。后來又想，至于復(fù)制構(gòu)造函數(shù)和賦值呢？查了一下才知道：如果我們只用基本數(shù)據(jù)類型，而沒有用指針或者引用作為數(shù)據(jù)成員，此時就不需要自己寫這些函數(shù)。所以一般情況下，我們通常都寫上這幾個構(gòu)造函數(shù)！

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