数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法

<h2>算法复杂度主方法</h2>

有时候，我们要评估一个算法的复杂度，但是算法被分散为几个递归的子问题，这样评估起来很难，有一个数学公式可以很快地评估出来。

<h2>一、复杂度主方法</h2>

主方法，也可以叫主定理。对于那些用分治法，有递推关系式的算法，可以很快求出其复杂度。

定义如下：

<span class="img-wrap"></span>

如果对证明感兴趣的可以翻阅书籍：《算法导论》。如果觉得太难思考，可以跳过该节。

由于主定理的公式十分复杂，所以这里有一种比较简化的版本来计算：

<span class="img-wrap"></span>

<h2>二、举例</h2> <ol><li>二分搜索，每次问题规模减半，只查一个数，递推过程之外的查找复杂度为<code>O(1)</code>，递推运算时间公式为：<code>T(n) = T(n/2) O(1)</code>。</li> <li>快速排序，每次随机选一个数字作为划分进行排序，每次问题规模减半，递推过程之外的排序复杂度为<code>O(n)</code>，递推运算时间递推公式为：<code>T(n) = 2T(n/2) O(n)</code>。</li> </ol>

按照简化版的主定理，可以知道：

二分查找：<code>a = 1，b = 2，d = 0</code>，可以知道<code>a = b^d</code>，所以二分查找的时间复杂度为：<code>O(logn)</code>。

快速排序：<code>a = 2，b = 2，d = 1</code>，可以知道<code>a = b^d</code>，所以快速排序的时间复杂度为：<code>O(nlogn)</code>。

强调：并非所有递推关系式都可应用主定理，但是大部分情况下都可以。

因为需要较多的数学知识，所以我们只简单介绍到这里。

<h2>延伸-计算理论：P和NP问题</h2>

在计算机科学中，有一个专门的分支研究问题的可计算性，叫做计算理论。

我们用计算机算法来解决一个问题，如果一个问题被证明很难计算，或者只能暴力枚举来解决，那么我们就不必花大力气去质疑使用的算法是不是错了，为什么这么慢，计算怎么久都没出结果，到底有没有更好的算法。

计算机科学把一个待解决的问题分类为：<code>P</code>问题，<code>NP</code>问题，<code>NPC</code>问题，<code>NP-hard</code>问题。

<h2>一、P 和 NP 问题</h2>

类似于<code>O(1)</code>，<code>O(logn)</code>，<code>O(n)</code>等复杂度，规模<code>n</code>出现在底数的位置，计算机能在多项式时间解决，我们称为多项式级的复杂。

类似于<code>O(n!)</code>，<code>O(2^n)</code>等复杂度，规模<code>n</code>出现在顶部的位置，计算机能在非多项式时间解决，我们称为非多项式级的复杂度。

如果一个问题，可以用一个算法在多项式时间内解决，它称为<code>P</code>问题(<code>P</code>为<code>Polynominal</code>的缩写，多项式)。

比如求1加到100的总和，它的时间复杂度是<code>O(n)</code>，是多项式时间。

然而有些问题，只能用枚举的方式求解，时间复杂度是指数级别，非多项式时间，但是只要有一个解，我们能在多项式时间验证这个解是对的，这类问题称为<code>NP</code>问题。

也就是说，如果我们只能靠猜出问题的一个解，然后可以用多项式时间来验证这个解，这些问题都是<code>NP</code>问题。

所以，按照定义，所有的<code>P</code>问题都是<code>NP</code>问题。

计算理论延伸出了图灵机理论，自动机=算法。

有两种自动机，一种是确定性自动机，机器从一个状态到另外一个状态的变化，只有一个分支可以走，而非确定性自动机，从一个状态到另外一个状态，有多个分支可以走。<code>P</code>问题都可以用两种机器来解决，当非确定性自动机退化就变成了确定性自动机，而<code>NP</code>问题只能用非确定性自动机来解决。

自动机对<code>N</code>和<code>NP</code>问题的定义：

可以在确定性自动机以多项式时间解决的问题，称为<code>P</code>问题，可以在多项式时间验证答案的问题称为<code>NP</code>问题。而<code>NP</code>问题是可以在非确定型自动机以多项式时间解决的问题（<code>NP</code>两字为<code>Non-deterministicPolynomial</code>的缩写，非确定多项式）。

数学，计算机科学，哲学，三个学科其实交融在一起，自动机是一台假想的机器，世界其实也可以认为是一个假想的机器，所以世界可以等于一台自动机吗，大家可以发挥想象力，在以后的日子里慢慢体会，建议购买书籍《计算理论》补习相关知识。

<h2>二、NPC 和 NP-hard 问题</h2>

存在这样一个<code>NP</code>问题，所有的<code>NP</code>问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的<code>NP</code>问题都解决了。其定义要满足2个条件：

<ol><li>它得是一个<code>NP</code>问题。</li> <li>所有的<code>NP</code>问题都可以约化到它。</li> </ol>

这种问题称为<code>NP</code>完全问题（<code>NPC</code>）。按照这种定义，<code>NP</code>问题要比<code>NPC</code>问题的范围广。

那什么是<code>NP-hard</code>问题，其定义要满足2个条件：

<ol><li>所有的<code>NP</code>问题都可以约化到它。</li> <li>它不是一个<code>NP</code>问题。</li> </ol>

也就是说，<code>NP-hard</code>问题更难，你只要解决了<code>NP-hard</code>问题，那么所有的<code>NP</code>问题都可以解决。但是，这个问题本身不是一个<code>NP</code>问题，也就是解不能在多项式时间内被验证。

比如你有一个交际网，每个人是一个节点，认识的人之间相连。你要通过一个最快、最省钱、最能提升你个人形象、最没有威胁、最不影响你日常生活的方式认识一个萌妹，你怎么证明你认识这个萌妹是最省钱的呢？-来自知乎回答。

我们一旦发现一个问题是<code>NPC</code>问题，那么我们很难去准确求出其解，只能暴力枚举，靠猜。

<h2>三、总结</h2>

各类问题可以用这个图来表示：

<span class="img-wrap"></span>

"<code>P=NP</code>" 问题的目标，就是想要知道<code>P</code>和<code>NP</code>这两个集合是否相等。为了证明两个集合（<code>A</code>和<code>B</code>）相等，一般都要证明两个方向：

<ol><li> <code>A</code>包含<code>B</code>。</li> <li> <code>B</code>包含<code>A</code>。</li> </ol>

我们已经说过<code>NP</code>包含了<code>P</code>。因为任何一个非确定性机器，都能被当成一个确定性的机器来用。你只要不使用它的“超能力”，在每个分支点只探索一条路径就行。

所以 "<code>P=NP</code>" 就在于<code>P</code>是否也包含了<code>NP</code>。也就是说，如果只使用确定性计算机，能否在多项式时间之内，解决所有非确定性计算机能在多项式时间内解决的问题。

<h1>系列文章入口</h1>

我是陈星星，欢迎阅读我亲自写的 数据结构和算法(Golang实现)，文章首发于 阅读更友好的GitBook。

<ul><li>数据结构和算法(Golang实现)(1)简单入门Golang-前言</li> <li>数据结构和算法(Golang实现)(2)简单入门Golang-包、变量和函数</li> <li>数据结构和算法(Golang实现)(3)简单入门Golang-流程控制语句</li> <li>数据结构和算法(Golang实现)(4)简单入门Golang-结构体和方法</li> <li>数据结构和算法(Golang实现)(5)简单入门Golang-接口</li> <li>数据结构和算法(Golang实现)(6)简单入门Golang-并发、协程和信道</li> <li>数据结构和算法(Golang实现)(7)简单入门Golang-标准库</li> <li>数据结构和算法(Golang实现)(8.1)基础知识-前言</li> <li>数据结构和算法(Golang实现)(8.2)基础知识-分治法和递归</li> <li>数据结构和算法(Golang实现)(9)基础知识-算法复杂度及渐进符号</li> <li>数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法</li> <li>数据结构和算法(Golang实现)(11)常见数据结构-前言</li> <li>数据结构和算法(Golang实现)(12)常见数据结构-链表</li> <li>数据结构和算法(Golang实现)(13)常见数据结构-可变长数组</li> <li>数据结构和算法(Golang实现)(14)常见数据结构-栈和队列</li> <li>数据结构和算法(Golang实现)(15)常见数据结构-列表</li> <li>数据结构和算法(Golang实现)(16)常见数据结构-字典</li> <li>数据结构和算法(Golang实现)(17)常见数据结构-树</li> <li>数据结构和算法(Golang实现)(18)排序算法-前言</li> <li>数据结构和算法(Golang实现)(19)排序算法-冒泡排序</li> <li>数据结构和算法(Golang实现)(20)排序算法-选择排序</li> <li>数据结构和算法(Golang实现)(21)排序算法-插入排序</li> <li>数据结构和算法(Golang实现)(22)排序算法-希尔排序</li> <li>数据结构和算法(Golang实现)(23)排序算法-归并排序</li> <li>数据结构和算法(Golang实现)(24)排序算法-优先队列及堆排序</li> <li>数据结构和算法(Golang实现)(25)排序算法-快速排序</li> <li>数据结构和算法(Golang实现)(26)查找算法-哈希表</li> <li>数据结构和算法(Golang实现)(27)查找算法-二叉查找树</li> <li>数据结构和算法(Golang实现)(28)查找算法-AVL树</li> <li>数据结构和算法(Golang实现)(29)查找算法-2-3树和左倾红黑树</li> <li>数据结构和算法(Golang实现)(30)查找算法-2-3-4树和普通红黑树</li> </ul> 到此这篇关于“数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法
golang sdk后端怎么用_Golang资深后端工程师需要了解的知识点
计算机基础知识-计算机组成与原理
php程序员需要会什么技术？
python怎么做大数据分析
golang 大数据平台_从数据仓库到大数据平台再到数据中台
python人工智能需要学什么
各种排序算法小结
学习Python却没看过这几本书，你就OUT了
Go从入门到精通系列视频之go编程语言密码学哈希算法