计算复杂度-解决现实生活中的问题

计算复杂度是对特定算法所花费的计算时间的度量。在一个特定问题有多种算法可用的场景中，任何特定算法的有效性都是根据时间限制来衡量的。这是通过将算法分解为基本步骤，然后对每个步骤进行计数来实现的。因此，步骤越多，复杂性就越大。例如，如果我们对两个5位二进制数进行异或运算，所走的步数是5，如果对一个100位二进制数重复同样的过程，所走的步数就会增加到100。这两种情况采用的算法是相同的;复杂度是由数字的大小决定的。

当我们说数字n的大小时，它被定义为表示以2为基数的“n”所需的二进制位数。例如，以10为底的5用二进制表示时采用101的形式，因此n = 3。类似地，20由10100表示₂所以n = 5。现在，如果我们对任意两个大小为n=b的数字进行异或，所走的步数将是“b”。因此，我们可以说，XORing这些数字的计算复杂度为O(b)。这可以应用于更简单的应用，如加法，其中如果我们要将两个n位数相加，当我们从右向左接近时，所采取的最小步骤数(忽略从前一步开始的任何结转)将等于n。这是无法避免的，因为我们需要知道每一个数字才能相加。回到上面所述的异或例子，如果我们要将数字的大小增加一倍，我们最终会将所需步骤的大小增加一倍，从而增加所需的时间。需要考虑的重要一点是，计算复杂度不依赖于机器的能力，换句话说，它与实现无关。这个因素变得很重要，因为不同的机器在处理相同的“b”基本步骤时可能需要不同的时间。另一个需要考虑的要点是，对于任何计算复杂度定义为O(b)的算法，如果我们将问题的大小乘以X，计算时间也将具有乘以X的相同效果。

图片提供:freedigitalphotos.net, ddpavumba

在复杂性理论中，大O符号用于描述函数的渐近行为。它告诉你函数增长的速率。函数增长的速率称为阶，因此用字母O作为它的符号。设f(x)和g(x)是两个用实数定义的函数。那么大O符号将表示为:

f(x) = O(g(x))(对于x属于实数)当且仅当存在某些常数N和C使得

|f(x)| <= C|g(x)| for all x>N

基本上，这意味着我们的函数不能比定义其随时间复杂度的函数增长得更快。

常用的函数g(x)描述随时间变化的函数如下，按增长速率递增(c为某常数)

O(1)常数

O (log (n)对数

O (log (n）)^c) polylogarithmic

O (n)线性

O (n²)二次

O (n^c)多项式

O (cⁿ)指数

如上所述，当涉及到加法时，两个二进制数相加的复杂度为O(b)。然而，如果我们将这些数字相乘，复杂度就变成了O(b)²)．我们可以举一个简单的例子来说明这种变化。假设我们要把34和56两个数相乘。这将涉及4个基本步骤的乘法，然后进行相应的调整，以得到最终结果。因此，这种情况下的复杂度为O(2)²)．类似地，如果我们将要相乘的数字的比特大小增加一倍，所需的时间就变为O[(2b)²[答案]c²)．

因此，复杂性理论基本上是根据解决问题时面临的困难程度对问题进行分类的。

这就引出了P和NP问题的概念:

1.确定性多项式时间(P)型

如果至少有一个算法可以解决一个问题，那么这个问题基本上就属于P(多项式时间)类;算法所采用的步骤数受“n”的多项式限制，其中n给出所使用的输入的长度。

如果对于给定的输入，完成算法所需的步数为O(n)，则现有的或新创建的算法被称为遵守多项式时间^k)对于某个非负整数k，其中k表示所提供输入的复杂度。采用多项式时间的算法被认为是快速、可行和高效的。大量的日常数学应用，如加法、减法、乘法和除法，以及平方根、对数和幂可以使用多项式时间来执行。

在确定性方法中产生的一个特定的术语是算法的时间复杂度。它将任何算法所花费的时间作为表示用户或任何其他来源提供的输入的字符串长度的函数进行测量。

算法的时间复杂度通常用大O符号表示，如上所述。它消去了所有系数和其他低阶项。当一个算法以这种方式表示时，我们可以说它的时间复杂度已经被描述了渐近也就是说，它的输入大小可以自由地接近无穷大。为了说明这一点，我们可以借助一种算法，其中所有大小的输入所需的时间n最多为5n^3.+ 3n．因此，该算法的渐近时间复杂度为O(n^3.）

下面是我们在日常使用中发现的几个多项式时间算法的例子:

• 在计算机科学中，快速排序算法应用于nintegers在最大Cn处执行²对给定常数的运算次数C．因此，运行时间用O(n)表示²)，这使得它成为一个多项式时间算法。
• 同样如上所述，加法、减法、乘法、除法等算术运算可以用多项式时间表示

2.非确定性多项式时间(NP)类型

NP问题是一个具有解、解的输入和一个在多项式时间内运行的验证器的问题。验证者必须同时考虑输入和对应的解决方案，并告诉用户它们是否同步。

NP本质上由所有决策问题的集合组成，其中问题的状态，无论是“是”还是“否”，都必须由有效的可验证的证据来支持，以证明它确实如此。实际上，这些证明必须是验证在确定性图灵机的帮助下，以多项式时间计算。NP以更正式的方式等价地定义，表示所有此类决策问题的集合，其中“是”实例已被非确定性图灵机在多项式时间内接受。为了衡量上述两个定义的等价性，我们可以参考这样一个事实，即在图灵机这样的非确定性机器上的算法被分为两个阶段——第一个阶段涉及对解决方案进行最接近的猜测，这再次以非确定性的方式生成;第二阶段使用确定性算法来验证或拒绝上述猜测，作为当前问题的有效解决方案

非确定性问题解决的一个极好的例子来自于“因式分解”，其中需要确定特定大数N的因子(例如A *b=N)，除非数字本身和1。理论分析人士多次观察到，如果我们把两个千位数的数字放在计算机中相乘，几乎不需要几秒钟就能得到结果，而如果我们把这个输出再次输入计算机，让它分解成因数，计算机可能要数百万年才能得出有效的解。这就提出了一个问题，即为什么我们需要经历如此多的痛苦才能得出如此大量的因素。事实证明，答案是至关重要的，它有可能改变一个经济体的状态。假设我们的一个朋友想要冒充一家银行。与几年前不同的是，银行之间的交易是通过卡车运输的金砖进行的，而现在的交易是通过受到严格保护的连接，通过在线资金转账完成的。事实证明，他们用来保护交易安全的加密算法叫做RSA。在RSA中，每一方都有一个由两个数字p和q组成的密钥，它们都是大素数，然后它们有一个公钥，n等于p*q。该公钥向所有人发布，以便其他人能够通过该网络发送消息，而这些消息将由使用该公钥的合作方解密。现在假设我们的朋友想在这里进行干预。 He is in charge of an efficient verifier which is capable of performing large divisions. He has n and then he obtains a P_猜一猜哪个给出n% P_猜一猜= 0

3.指数的问题

EXP指的是可以在指数时间内解决的问题集。指数时间算法是一种时间上界为2poly(n)的算法，其中poly(n)是n的多项式，即T(n)以O(2)为界^nk)对于某个常数k。N* N的棋盘问题是EXP类型的问题。它不能在多项式时间内解出来。

R指的是可以在有限范围内解决的问题。这些都是基本可以解决的问题。R为递归函数。可以在有限时间内用递归算法求解的问题就属于这一类。然而，可解决的问题只占我们现有问题的很小一部分。其余的问题在数学上是无法解决的。

现实生活问题的复杂性分析:

步骤1:为了在现实生活中应用计算复杂性，我们首先需要在不改变其复杂性的情况下，将现实生活中的问题转化为一个是非问题。转换需要输入中的阈值。问题通常有两种类型——可行性问题或满意度问题。如。安排生产设施，时间表和生产过程的最后期限，并安排工作不延迟。下面是现实生活中的一些标准例子:

单机截止日期调度实例当前位置我们正在根据加工时间的可行性来安排机器操作，以便在最后期限前完成。

设处理时间定义为ti，作业的最后期限为di，其中i从1到n不等。

那么我们的问题可以表示为:

问题:我们是否有一个i从1到n的开始时间si>0集合，使得sj属于i≠j的集合[si, si+ti)，以便在满足每个任务si+ti <= di的截止日期的约束下，一个开始时间与另一个开始时间不冲突?

双机线路平衡实例:我们这里的任务是在已知加工时间的情况下，在两台机器K和J之间平均分配作业。可以表示为:

设处理时间的集合为ti，其中i从1到n。设存在一个数字v

问题:我们能否将指标i =1到n进行除法，使得进程在机器K上花费的时间与进程在机器J上花费的时间之差小于或等于v ?

上述问题的一个更受限制的版本是当需要一个完美的平衡时，即v=0。

那么问题将是:我们能否将指标i =1到n进行除法，使得进程在机器K上花费的时间等于进程在机器J上花费的时间。

这个等时间问题叫做二分区问题．这个问题比双机线平衡更难处理，因为它的限制更大

步骤2因此，下一步我们需要了解的是如何发现任何问题的复杂性。因此，导致问题变得困难的一些基本因素如下:当需要对资源进行完美的划分时，对考虑当前位置和以前位置的决策进行排序，将一组对象分成子集，其中每个子集都存在约束，找出满足某个属性的最大子结构，最小化或最大化集合的并集和交集。用限制值代替阈值有时也会改变其复杂性。所以我们在这样做的时候需要非常小心。重要的是要弄清楚是什么让问题变得困难，可能很难达到平衡。两个分区就是一个例子。另一方面，一个问题很容易平衡一切，但很难最小化没有获得完美组合的负面影响。独立集合要求多边形顶点的最大大小集合，使它们中没有两个被边连接，这是第二类的例子。因此，确定类型并相应地工作。

当我们解决的问题越来越多时，我们就会发展出一种识别问题中困难部分的直觉能力。让我们看看如何识别NP困难问题。首先确定一个困难的问题，然后想一个简单的问题进行对比。比较这两个问题，找出使困难问题变得简单的方法。以下是一些约束的例子:

整数规划(IP):在Ax<=b的约束下，最大化c*x，其中x为整数。

对比:线性规划很简单，当约束只有两个固定维度中的一个(单模)时，整数规划也很简单。这里的尺寸是指序号。变量和总约束。

双机加权流量时间最小化:给定两个并行处理器和一组具有单独处理时间和权重的作业，找到一个使加权完成时间和最小的调度。

对比:如果给定的权重或时间相等，那么问题对于任何不都很容易。的处理器。每次运行同等权重或同等处理器约束。

Steiner树:给定一个图G = (V, E)、边长和顶点V的子集S，在G中找到一个总长度最小且包含S的树(该树可以包含V - S中的顶点;试着连接平面上一个正方形的顶点。)

对比:最小生成树问题，其中S =V，很简单。

通常情况下，困难的问题可以用动态规划来解决。如果动态规划没有帮助，那么其他方法，如现成的数学软件或重型数学规划方法和启发式可以帮助。

简单的问题可以用线性规划、单纯形法和整数规划等方法来解决。

减少:

在计算复杂度中，减少被定义为将一种类型的问题转化为另一种类型的问题。如果X的算法也可以用来解决Y，那么X问题就可以简化为Y问题。这意味着问题Y比x更容易解决。我们使用的约简有两种类型:多一约简和图灵约简。多对一简化是通过将一个问题的实例映射到另一个问题的实例来实现的。另一方面，图灵约简是在解决一个问题的前提下，假设另一个问题很简单。图灵约简比多一约简更强。然而，更强的约简在分离问题时并不有效，尽管它们更容易设计。

当减法很容易时，它是有用的。例如，一个困难的np完全问题可以简化为一个微不足道的问题。此外，它还可以将不可计算的问题转化为可判定的问题。约简用于诸如停止问题等问题，以证明语言是不可判定的，即当给定字符串w的输入(H(M,w))时，图灵机M将停止。这种语言据说是不可分辨的。如果F(M)是确定图灵机的输入语言是否为空的问题那么通过H的约简，我们知道F是不可定的。

结论:

对计算复杂度的基本理解有助于经理确定解决手头现实问题所需的时间，并判断问题实例的实际规模。此外，算法的选择比硬件和数据结构的选择更重要。将问题分为易问题和np -难问题将告诉我们解决问题的可行方法。然后决定最终的方法还可以考虑其他方面，如规模、财务风险、理想的准确性和时间限制。计算复杂性是一个不可避免的现象。大多数问题都很难解决。但如果我们足够认真地研究，现实的案例几乎每次都很简单。作为一名管理者，对计算复杂度的基本学习和应用主要帮助我们解决与操作相关的问题。正如在上面的文本中所引用的某些例子，如机器调度，满足最后期限，最小化延迟作业，同样，我们可以将其用于生产设施中的问题，并通过使用适用于特定类型的复杂性的适当方法来减少解决问题的时间。

本文由poja Punjabi和Manash Hazarika来自Kozhikode IIM

引用:

• http://en.wikipedia.org/wiki/Computational_complexity_theory
• http://theory.stanford.edu/~trevisan/notes/complexitynotes02.pdf
• http://www2.isye.gatech.edu/~ctovey/tovey.tutorial.pdf
• http://staff.science.uva.nl/~ulle/teaching/comsoc/2012/slides/comsoc-complexity-tutorial.pdf