标签: time-complexity

您将获得一个32位无符号整数数组,其长度最大为2 ³²,其中包含数组中一半以上条目的属性等于N,对于某些32位无符号整数N.查找N查看每个数字在数组中只使用一次并使用最多2 kB的内存.

您的解决方案必须是确定性的,并保证找到N.

MSDN声明以下SortedSet(T).Add方法:

如果Count小于内部阵列的容量,则此方法是O(1)操作.

有人可以解释"怎么样"？我的意思是在添加新值时,我们需要找到一个正确的位置来添加一个值(将其与另一个值进行比较),内部实现看起来像一个具有O(log N)插入复杂度的"红黑树".

所以,我们看到了很多斐波纳契问题.我个人非常讨厌他们.很多.不止一切.我认为如果我们可以让任何人都不可能再次将其用作面试问题,那就太好了.让我们看看有多接近O(1)我们可以得到斐波那契.

这是我的开始,几乎来自维基百科,当然还有足够的空间.重要的是,这个解决方案将引爆任何特别大的fib,它包含一个相对天真的power函数使用,如果你的库不好,它会把它放在最坏的O(log(n)).我怀疑我们可以摆脱电源功能,或至少专攻它.有人帮忙吗？除了使用查找表的有限*解决方案之外,是否存在真正的O(1)解决方案？

http://ideone.com/FDt3P

#include <iostream>
#include <math.h>
using namespace std; // would never normally do this.

int main()
{
int target = 10;
cin >> target;
// should be close enough for anything that won't make us explode anyway.
float mangle = 2.23607610; 

float manglemore = mangle;
++manglemore; manglemore = manglemore / 2;
manglemore = pow(manglemore, target);
manglemore = manglemore/mangle;
manglemore += .5;
cout << floor(manglemore);

}

*我知道,我知道,这足以满足斐波纳契的任何零实际用途.

是否有任何Python复杂性参考？例如,在cppreference中,对于许多函数(例如std :: array :: size或std :: array :: fill),有一个复杂性部分,用容器大小的线性或常量来描述它们的运行复杂性..

我希望在python网站上出现相同的信息,或许至少对于CPython实现.例如,在列表引用中,list.insert我希望看到复杂性:线性 ; 我知道这种情况(和许多其他容器相关的操作)在这里,但许多其他情况不是.这里有一些例子:

• 什么是复杂性tuple.__le__？似乎在比较两个大小的元组时n,k复杂性是关于O(min(n,k))(然而,对于小n的它看起来不同).
• 什么是复杂性random.shuffle？它似乎是O(n).它也出现了复杂random.randint的O(1).
• __format__字符串方法的复杂性是什么？它看起来与输入字符串的大小呈线性关系; 然而,当数也增长有关生长参数(比较("{0}"*100000).format(*(("abc",)*100000))用("{}"*100000).format(*(("abc",)*100000))).

我知道(a)这些问题中的每一个都可以单独回答,(b)可以查看这些模块的代码(即使有些是用C语言编写的),(c)StackExchange不是python邮件用户请求列表.所以:这不是文档功能请求,只是两个部分的问题:

1. 你知道这样的资源是否存在吗？
2. 如果没有,你知道要求的地方是什么,或者你能说出我不需要的地方吗？

我们以Merge Sort的这个实现为例

void mergesort(Item a[], int l, int r) {
if (r <= l) return;
int m = (r+l)/2;
mergesort(a, l, m);  ------------ (1)
mergesort(a, m+1, r); ------------(2)
merge(a, l, m, r);

a)此合并排序的时间复杂度为O(nlg(n)).并行化(1)和(2)会带来任何实际收益吗？从理论上讲,似乎在并行化后,你最终会得到O(nlg(n).但实际上我们可以获得任何收益吗？

b)此合并排序的空间复杂度为O(n).但是,如果我选择使用链接列表执行就地合并排序(不确定是否可以合理地使用数组),空间复杂度将变为O(lg(n)),因为您必须考虑递归堆栈帧大小？我们可以将O(lg(n))视为常数,因为它不能超过64吗？我可能在几个地方误解了这一点.64的意义究竟是什么？

c)http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html说合并排序需要使用链表的恒定空间.怎么样 ？他们对待O(lg(n)不变？

d)[添加以获得更多清晰度]对于空间复杂度计算,假设输入数组或列表已经在内存中是公平的吗？当我进行复杂度计算时,我总是计算除了已经输入的空间之外我将需要的"额外"空间.否则空间复杂性将始终为O(n)或更差.

在计算机科学中,据说哈希表的插入,删除和搜索操作具有O(1)的复杂度,这是最好的.所以,我想知道,为什么我们需要使用其他数据结构,因为散列操作如此之快？为什么我们不能简单地使用哈希/哈希表来处理所有事情？

我正在玩一款拥有武器锻造组件的游戏,你可以将两种武器结合起来获得新武器.武器组合的绝对数量(参见http://www.gamefaqs.com/ps/914326-vagrant-story/faqs/8485上的 "6.1.刀片组合表" )很难弄清楚你最终可以创造出什么通过反复锻造你当前的武器,所以我尝试编写一个程序来为我做这个.我给它一份我目前拥有的武器清单,例如:

• 弗朗西斯
• tabarzin
• 短剑的一种

它给了我所有可以伪造的武器清单:

• 球梅斯
• chamkaq
• 短剑
• 弗朗西斯
• 大新月
• 扔刀

问题是我使用的蛮力算法扩展得非常差; 计算7种起始武器的所有可能武器需要大约15秒,而计算8种起始武器需要几分钟.我希望它能够计算多达64种武器(你可以同时拥有的最大值),但我认为我没有足够长的时间看到结果.

function find_possible_weapons(source_weapons)
{
    for (i in source_weapons)
    {
        for (j in source_weapons)
        {
            if (i != j)
            {
                result_weapon = combine_weapons(source_weapons[i], source_weapons[j]);

                new_weapons = array();
                new_weapons.add(result_weapon);
                for (k in source_weapons)
                {
                    if (k != i && k != j)
                        new_weapons.add(source_weapons[k]);
                }
                find_possible_weapons(new_weapons);
            }
        }
    }
}

用英语:我从源武器列表中尝试两种武器的组合.对于这些组合中的每一个,我创建了一个新的列表,列出了我在该组合之后所拥有的所有武器(也就是说,新组合的武器加上除了我合并的两个以外的所有武器),然后我重复这些新列表的步骤.

有一个更好的方法吗？

请注意,以相反顺序组合武器可以改变结果(Rapier + Firangi =短剑,但Firangi + Rapier = Spatha),所以我不能跳过j循环中的那些反转.

编辑:这是我上面给出的测试示例的细分,以显示算法正在做什么.括号中的一行显示组合的结果,以下行是作为结果创建的新武器列表:

francisca,tabarzin,kris
[francisca + tabarzin …

我刚刚发现这个奇怪的发现，在正常数学中，n*logn 会小于 n，因为 log n 通常小于 1。那么为什么 O(nlog(n)) 大于 O(n)？（即为什么 nlogn 被认为比 n 花费更多的时间）

Big-O 是否遵循不同的系统？

我想知道用c ++构建的pow()函数的最坏情况时间复杂度是多少？

从链表标签维基摘录:

链表是一种数据结构,其中元素包含对下一个(以及可选的前一个)元素的引用.链接列表提供在任何位置的O(1)插入和移除,O(1)列表串联,以及前(和可选后)位置的O(1)访问以及O(1)下一个元素访问.随机访问具有O(N)复杂性并且通常是未实现的.

^{(强调我的)}

我很惊讶地看到这个 - 如何在一个随机索引中插入一个复杂度低于简单读取索引的列表？

所以我查看了源代码java.util.LinkedList.该add(int, E)方法是:

public void add(int index, E element) {
    addBefore(element, (index==size ? header : entry(index)));
}

该addBefore(E, Entry<E>方法只是指针重新分配,但也有entry(int)方法:

if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e …