标签: complexity-theory

我正在使用Ukkonen的算法来构建后缀树,但是我不理解作者对其线性时间复杂性的解释的某些部分.

我已经学会了算法并对其进行了编码,但是我用作信息主要信息源的文章(链接波纹管)在某些部分有点令人困惑,因此对我来说,为什么算法是线性的并不是很清楚.

有帮助吗？谢谢.

链接到Ukkonen的论文:http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

查找数字阶乘的递归程序的复杂性是多少n？我的预感是可能的O(n).

通常,一些答案提到给定的解决方案是线性的,或者另一个解决方案是二次的.

如何区分/识别什么是什么？

对于像我这样仍然不知道的人,有人可以解释这个,这是最简单的方法吗？

所以,

问题

我有一个关于确定两个点是否连接在2D平面上的算法的问题.我有:

• 2D线阵列.每条线都以其起始端2D点限制.每个点都是两个元素的简单数组[x,y]- 即每条线看起来像['start'=>[X0, Y0], 'end'=>[X1, Y1]]这条线被命名为L.线可以彼此属于一个(即一个可以是另一个的一部分),它们可以仅与一个点相交等 - 即在2D平面上没有它们的限制.但是线不能是一个点 - 即线的起点不能等于线的终点.
• 两点S和E,即阵列[Xs, Ys]和[Xe, Ye]

现在,所有线L都在平面上绘制.然后,S和E也拉,我需要回答的问题- 可以从S为达到ê不以L任何线的交叉？而且,更具体一点 - 哪种算法最优？通过"可达到"我的意思是,有在飞机上的方式从S以E没有任何交集的线L-和,事业,这种方法可以是任何东西,而不仅仅是行.

样品

-as你看,在样品S和E未连接.同样在样本中存在一条线完全属于另一条线(灰线和紫线)的情况 - 以及一条线在另一条线(绿线和玫瑰线)上具有开始/结束的情况.

我的方法

目前,我有非确定性多项式(NP)算法来做到这一点.它的步骤是:

• 查找每对线的所有交叉点.
• 从第一步的点创建新的一组线.如果两条线有一个交叉点,则每条新线的起点将有4条新线与交叉点 - 如果第一条线在第二条线上有它的开始/结束,它可以是3条新线 - 或者它可以是2条新线如果第一行的开头/结尾与第二行的开头/结尾完全匹配.即:

因此,第一种情况将导致4条新线,3条新线中的2-4例和2条新线中的5例.(线是[A, B]和[C, D])

• 接下来,在第2步的第一步中,我搜索所有多边形.多边形是一个闭合线集(即它保持封闭的部分区域)
• 我正在确定S包含这些多边形的子集S.要做到这一点,我正在使用简单的算法 - 计算多边形边缘的交点数和从 …

确定1到N范围内缺失值的常见访谈问题已经完成了一千多次.变化包括2个缺失值,最多K个缺失值.

示例问题:范围[1,10](1 2 4 5 7 8 9 10)= {3,6}

以下是各种解决方案的示例:

简单的面试问题变得更难:给出数字1..100,找到丢失的数字

我的问题是,看到一个缺失值的简单情况是O(n)复杂性,并且较大情况的复杂性收敛于大于O(nlogn)的大小:

通过对范围进行排序(mergesort)并迭代它来观察缺失的元素,难道只是更容易回答这个问题吗？

该解决方案应该不超过O(nlogn),并且能够解决1到N之外的范围的问题,例如10到1000或-100到+100等......

是否有理由相信上述SO链接中的给定解决方案将比基于排序的解决方案更好地存在大量缺失值？

注意:对于这个问题,似乎有很多常见的解决方案,假设只有一个数论的方法.如果在S/E采访中被问到这样一个问题,使用更多的计算机科学/算法方法是不谨慎的,假设该方法与数论解决方案的复杂性相同......

更多相关链接:

• https://mathoverflow.net/questions/25374/duplicate-detection-problem
• 如何判断数组是否是O(n)中的排列？

日志库10功能的复杂性是多少？

我需要关于棘手问题的专家建议.

场景是:

• 电子商务网站
• 很多产品
• 很多折扣混合在这些产品上

产品由唯一的ProductID标识并具有销售价格.很经典的场景.该产品还可以有一个或多个折扣.

折扣可以是不同类型的.折扣的一个例子是:

• 在一组产品中购买两件或两件以上产品,每件产品可享受X折优惠

订单项只能获得一个折扣,因此一旦订单项打折,就无法获得其他折扣.

测试用例数据:

• 产品-1:10美元
• 产品-2:10美元
• 产品-3:50美元
• 产品-4:100美元

折扣-A:购买两件或两件以上产品可获得以下任何产品20%的优惠

• 产品-1
• 产品-2
• 产品-3
• 产品-4

折扣-B:购买产品并享受以下产品50%的折扣

• 产品-3

测试场景1:

购物篮:包含以下行项目:

• 产品-1
• 产品-3
• 产品-4

计算#1:

• 折扣-A:产品-1,产品-3,产品-4 = $ 2 + $ 10 + $ 20 = $ 32
  • =总共32美元

计算#2:

• 折扣-A:产品-2,产品-4 = $ 2 + $ 20 = $ 22
• 折扣-B:产品-3 = 25美元
  • = 22美元+ 25美元=总共节省47美元

这意味着Discount-A和Discount-B的组合将为客户提供最佳折扣.

测试场景2:

购物篮:包含以下行项目:

• 产品-3
• 产品-4

计算#1:

• 折扣-A:产品-3,产品-4 = 10美元+ …

我正在学习计算复杂性的课程,到目前为止,它给人的印象是它对开发人员没什么帮助.

我可能错了,但如果你以前走过这条道路,你能否提供一个例子,说明复杂性理论如何帮助你完成工作？非常感谢.

我一直认为复杂性:

1 + 2 + 3 + ... + n 是O(n),并且将两个n乘n个矩阵求和为O(n ^ 2).

但是今天我从教科书中读到"通过前n个整数之和的公式,这是n(n + 1)/ 2",然后是:(1/2)n ^ 2 +(1/2) n,因此O(n ^ 2).

我在这里错过了什么？

假设我有一个STL set <int> s和一个int x,我怎么能计算出s少于的元素数x？

我正在寻找一个O(log n)(或类似的;任何比它更合理的O(n))解决方案;

我已经知道了std::distance(s.begin(), s.lower_bound(x)),但O(n)我相信,因为sets不是随机访问.