小角色，大心脏

某此报告会上，提到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，知识匮乏，前来充电；
• 希望多动脑，多动手，分享资源，共同学习，提高效率；