标签: asymptotic-complexity

Big-O表示法O(n)和Little-O表示法有o(n)什么区别？

想象一下,你在一座有猫的高楼里.这只猫可以在低矮的故事窗口中摔下来,但如果从高楼层抛出,它就会死亡.你怎么能用最少的尝试数来计算猫可以存活的最长时间？

显然,如果你只有一只猫,那么你只能线性搜索.先从一楼扔猫.如果它存活下来,从第二个扔掉它.最终,从地板f抛出后,猫会死.然后你知道楼层f-1是最大的安全楼层.

但是,如果你有一只以上的猫怎么办？您现在可以尝试某种对数搜索.让我们说这个版本有100层,你有两个相同的猫.如果你将第一只猫从50楼扔出去并且死亡,那么你只需要线性搜索50个楼层.如果您为第一次尝试选择较低楼层,则可以做得更好.假设您选择一次解决20个楼层的问题,并且第一个致命楼层是#50.在这种情况下,你的第一只猫将在从60楼死亡之前从20楼和40楼的飞行中幸存下来.你只需要分别检查楼层41到49.这总共有12次尝试,这比你试图使用二进制消除所需的50次要好得多.

一般来说,对于有2只猫的n层建筑来说,最好的策略和最坏情况的复杂性是什么？n楼和m猫怎么样？

假设所有猫都是等同的:它们都将从给定窗口的摔倒中幸存或死亡.此外,每一次尝试都是独立的:如果一只猫在跌倒时幸存下来,它就完全没有受到伤害.

这不是家庭作业,虽然我可能已经解决了一次学校作业.这只是一个异想天开的问题,今天突然出现在我脑海中,我不记得解决方案了.如果有人知道此问题的名称或解决方案算法的加分点.

我最初写了一个ArrayList并存储了唯一值(用户名,即Strings).我后来需要使用它ArrayList来搜索用户是否存在.这是O(n)为了搜索.

我的技术负责人希望我将其更改为a HashMap并将用户名存储为数组中的键,并将值存储为空Strings.

所以,在Java中 -

hashmap.put("johndoe","");

我可以通过运行来查看此用户是否存在 -

hashmap.containsKey("johndoe"); 

这是O(1)对的？

我的主管说这是一种更有效的方法来实现这一点,这对我来说很有意义,但是将hash/empty作为值放在hashmap中并将其中的元素作为键存放似乎有点过时了.

我的问题是,这是一个好方法吗？效率节拍ArrayList#contains或一般的阵列搜索.有用.我担心的是,我没有看到其他人在搜索后这样做.我可能在某个地方错过了一个明显的问题,但我看不到它.

我知道这个算法的大O复杂性O(n^2),但我不明白为什么.

int sum = 0; 
int i = 1; j = n * n; 
while (i++ < j--) 
  sum++;

即使我们j = n * n在开始时设置,我们在每次迭代期间递增i并递减j,所以迭代的结果数量是否应该小于n*n？

我有一个问题,我试着一次又一次地思考它......但是没有得到什么,所以在这里发布问题.也许我可以得到一些其他人的观点,试着让它发挥作用......

问题是:我们得到一个SORTED数组,它由一组偶数发生的值组成,除了一个,发生ODD次数.我们需要在log n时间找到解决方案.

在O(n)时间内很容易找到解决方案,但在log n时间执行它看起来相当棘手.

最近我在链表上遇到了一个有趣的问题.给出了单独排序的列表,我们必须从该列表中搜索一个元素.

时间复杂度不应超过O(log n).这似乎我们需要在此链表上应用二进制搜索.怎么样？由于链接列表不提供随机访问,如果我们尝试应用二进制搜索算法,它将达到O(n),因为我们需要找到列表的长度并转到中间.

有任何想法吗？

是否存在有关的.NET集合类的方法渐近复杂性(大O,其余)的任何资源(Dictionary<K,V>,List<T>等...)？

我知道C5库的文档包含了一些关于它的信息(示例),但我也对标准.NET集合感兴趣...(而且PowerCollections的信息也很好).

如果给出了编程问题中的上述条件并且我使用递归来解决它,那么我是否违反了约束条件？这可能是因为递归也使用堆栈？这样对吗？

检测线是否与凸多边形相交的O(n)算法包括检查多边形的任何边是否与线相交,并查看交点的数量是奇数还是偶数.

是否存在渐近更快的算法,例如O(log n)算法？

假设我有这个函数:( Haskell语法)

f x = (x,x)

该功能执行的工作(计算量)是多少？

起初我认为它显然是不变的,但是如果类型x不是有限的,那意味着x可以占用任意数量的内存？人们必须考虑到复制所做的工作x,对吗？

这让我相信函数完成的工作实际上是输入大小的线性.

这不是本身的功课,但是当我不得不定义函数完成的工作时:

f x = [x]

我相信哪个有类似的问题.