标签: complexity-theory

我正在寻找一些"推理规则"(类似于设置操作规则或逻辑规则),我可以用它来减少复杂或大小的SQL查询.有没有这样的东西？任何文件,任何工具？您自己找到的任何等价物？它在某种程度上类似于查询优化,但不是在性能方面.

说明不同:使用JOIN,SUBSELECTs,UNIONs(复杂)查询是否可以(或不)通过使用某些转换规则将其减少为更简单的等效SQL语句,从而产生相同的结果？

因此,我正在寻找SQL语句的等效转换,例如大多数SUBSELECT可以重写为JOIN的事实.

在.NET 4.0+中,类SortedSet<T>有一个名为的方法GetViewBetween(l, r),它返回树部件上的接口视图,其中包含指定的两个之间的所有值.鉴于它SortedSet<T>是作为红黑树实现的,我自然希望它能够及时运行O(log N).C++中的类似方法是std::set::lower_bound/upper_boundJava TreeSet.headSet/tailSet,它们是对数的.

然而,事实并非如此.以下代码在32秒内运行,而等效O(log N)版本GetViewBetween将使该代码在1-2秒内运行.

var s = new SortedSet<int>();
int n = 100000;
var rand = new Random(1000000007);
int sum = 0;
for (int i = 0; i < n; ++i) {
    s.Add(rand.Next());
    if (rand.Next() % 2 == 0) {
        int l = rand.Next(int.MaxValue / 2 - 10);
        int r = l + rand.Next(int.MaxValue / 2 - 10);
        var t = s.GetViewBetween(l, …

我知道Javascript中的unshift()和push()方法有什么区别,但我想知道时间复杂度有什么不同？

我想push()方法是O(1),因为你只是在数组末尾添加一个项目,但我不确定unshift()方法,因为,我想你必须"移动"所有其他现有的元素向前,我想是O(log n)或O(n)？

最近,我注意到有些人提到它std::list::size()具有线性复杂性.
根据一些 消息来源,这实际上是依赖于实现的,因为标准没有说复杂性必须是什么.此博客条目中
的评论说:

实际上,这取决于您使用的STL.Microsoft Visual Studio V6将size()实现为{return(_Size); 而gcc(至少在版本3.3.2和4.1.0中)将其作为{return std :: distance(begin(),end()); 第一个具有恒定速度,第二个具有o(N)速度

1. 所以我的猜测是因为VC++人群的size()复杂程度不变,因为自VC6以来Dinkumware可能不会改变这一事实.我在那儿吗？
   
2. 目前看起来像gcc什么？如果它真的是O(n),开发人员为什么选择这样做？

我刚想到,如果你对要排序的数据的分布(在统计意义上)有所了解,那么如果考虑到这些信息,排序算法的性能可能会受益.

所以我的问题是,是否有任何排序算法考虑到这种信息？他们有多好？

编辑:一个示例澄清:如果您知道数据的分布是高斯分布,则可以在处理数据时动态估计平均值和平均值.这将为您估算每个数字的最终位置,您可以使用它来将它们放置在最终位置附近.

编辑#2:我很惊讶答案不是一个维基链接到一个讨论这个问题的页面.这不是一个非常常见的情况(例如高斯情况)？

编辑#3:我正在为这个问题增加一笔赏金,因为我正在寻找明确的答案来源,而不是猜测.类似于"在高斯分布式数据的情况下,XYZ算法平均速度最快,正如Smith等人[1]所证实的那样".但欢迎任何其他信息.

注意:我会将赏金奖励给得票最高的答案.明智地投票!

假设我有两种算法:

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    //do something in constant time
  }
}

这很自然O(n^2).假设我也有:

for (int i = 0; i < 100; i++) {
  for (int j = 0; j < n; j++) {
    //do something in constant time
  }
}

这是 O(n) + O(n) + O(n) + O(n) + ... O(n) + = O(n)

似乎即使我的第二个算法是O(n),它也需要更长的时间.有人可以扩展吗？我提出它是因为我经常看到算法,例如,他们将首先执行排序步骤或类似的事情,并且在确定总复杂度时,它只是限制算法的最复杂元素.

Big O表示法中每个python设置操作的时间复杂度是多少？

我使用Python的set类型对大量项目进行操作.我想知道每个操作的性能将如何受到集合大小的影响.例如,添加和成员资格测试:

myset = set()
myset.add('foo')
'foo' in myset

谷歌搜索没有发现任何资源,但似乎合理的是,Python的集合实现的时间复杂性将被仔细考虑.

如果它存在,到一些链接像这将是巨大的.如果没有这样的东西,那么也许我们可以解决它？

用于查找所有设置操作的时间复杂度的额外标记.

每当我需要存储与特定类型的值(键值 - 例如字符串或其他对象)相关联的一些数据时,我通常使用C++ stdlib映射.stdlib映射实现基于树,它提供比标准数组或stdlib向量更好的性能(O(log n)).

我的问题是,你知道任何C++"标准"哈希表实现提供更好的性能(O(1))吗？类似于Java API中Hashtable类中可用的内容.

这是我在数据结构和每个讲座/ TA讲座的第一门课程,我们谈论O(log(n)).这可能是一个愚蠢的问题,但如果有人能够向我解释它究竟是什么意思,我会很感激!

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

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

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