小角色，大心臟

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

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

##P 問題：對一個問題，凡是能找到計算復雜度可以表示為多項式的確定算法，這個問題就屬于 P (polynomial) 問題。

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

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

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

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

從直覺上說，P<=NP<=NP-Complete<=NP-Hard，問題的難度遞增。但目前只能證明 P 屬于 NP，究竟 P=NP 還是 P 真包含于 NP 還未知。

不止一次，看到很多講技術的文章里面出現過這個詞語。在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.

在計算機領域，Bleeding Edge指一種最新的、因而也并非完美的技術。使用者為了它的新，就要拿穩定性和產量來冒險。它也指當今技術的每一步發展都越來越昂貴的趨勢。這個詞的發明者是一個超級數據庫的程序員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更要隱含一種風險的含義：和Cutting Edge相比，Bleeding Edge更要前衛一些。通常，一種技術如果要被稱作是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.
• 沒有公認——在達到同一目標的不同的技術道路之中，沒有人知道，究竟哪一條路會成為市場的最終選擇。
• 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.
• 缺乏認識——當一些機構開始對一項新技術或者新產品進行研發的時候，行業媒體甚至還沒有開始對此展開討論，無論是贊成，還是反對。
• 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.
• 遭到產業抵制——行業媒體和產業界已經對某項新技術或者新產品進行抨擊，但是一些組織和機構因為堅信其技術上的優越性而繼續努力完善之。

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.

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

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.

但是現在，在越來越多的普遍用法中，Bleeding Edge已經成為一個只是強調前衛性而沒有風險性的詞語。

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."

一個引用環境是：“當你選擇了Bleeding Edge的技術之后，你就不應該為此付出的代價而感到震驚。”

 

Bleeding

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

---

 

Question：編譯器會自動創建那些成員函數呢？什么情況下我們不需要自己寫這些函數呢？（學生問時，我說了三種，少了assignment operator）
Answer：constructor(構造函數);destructor(析構函數)；copy constructor(復制構造函數)；assignment operator(賦值操作符)
              以Human為例：
                     Human();//默認構造函數
                     ~Human();//析構函數
                     Human(const Human& p);//復制構造函數
                     Human & operator = (const Human & lvalue);//賦值操作符函數
               學生又問了既然編譯器給我們自動創建了這些構造函數，為什么我們還要重新自己定義呢？
               暈倒，我問“構造函數的作用是什么呢？” 答曰“初始化數據成員（因為無法在類里面給成員變量賦初值）” “僅僅如此嗎，如果需要實現一些功能呢，要不要在構造函數里寫？回答是肯定的”。至于其他幾個構造函數別有用途，另行討論；
               學生沒有示弱的意思，反問道“那什么情況下，我們不需要寫這些函數呢” 
                稍稍考慮了一下，“如果沒有寫構造函數，編譯器會自動生成一個不帶參數的構造函數即默認構造函數，析構函數類似”，暫時敷衍了一下。后來又想，至于復制構造函數和賦值呢？查了一下才知道：如果我們只用基本數據類型，而沒有用指針或者引用作為數據成員，此時就不需要自己寫這些函數。所以一般情況下，我們通常都寫上這幾個構造函數！

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