标签: big-o

假设我有两种算法:

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的集合实现的时间复杂性将被仔细考虑.

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

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

所以给出以下程序:

这个程序的时间复杂度是O(0)吗？换句话说,是0 O(0)？

我想在一个单独的问题,回答这个问题将阐明一些轻这个问题.

编辑:这里有很多好的答案!我们都同意0是O(1).问题是,0 O(0)也是？

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

O(n!)函数的示例(在代码中)是什么？应该参考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？

我对计算机科学很陌生。在讲座结束时，我的 AP 计算机科学老师提到在排序数组中查找指定值的比较模型是big omega (log n) ie ?(log n)，据我所知，这意味着它是不可能完成的这个任务比O(log n)快。为什么是这样？

int sum = 0;
for(int i = 1; i < n; i++) {
    for(int j = 1; j < i * i; j++) {
        if(j % i == 0) {
            for(int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
}

我不明白当 j = i, 2i, 3i ... 最后一个for循环如何运行 n 次。我想我只是不明白我们是如何根据if声明得出这个结论的。

编辑：我知道如何计算所有循环的复杂性，除了为什么最后一个循环根据 mod 运算符执行 i 次......我只是不明白它是如何的。基本上，为什么 j % i 不能上升到 i * i 而不是 i？

我感兴趣的是创建一个类似于堆栈的Java数据结构,它尽可能高效地支持以下操作:

• 推送,在堆栈顶部添加一个新元素,
• Pop,删除堆栈的顶部元素,
• Find-Max,返回(但不删除)堆栈的最大元素,和
• Find-Min,返回(但不删除)堆栈的最小元素,和

这个数据结构最快的实现是什么？我怎么能用Java编写它？

根据我的理解,我使用下面给出的邻接表将Dijkstra算法的时间复杂度计算为big-O表示法.它没有像它应该的那样出来,这让我逐步理解它.

1. 每个顶点可以连接到(V-1)个顶点,因此每个顶点的相邻边的数量是V-1.让我们说E代表连接到每个顶点的V-1边.
2. 在最小堆中查找和更新每个相邻顶点的权重是O(log(V))+ O(1)或O(log(V)).
3. 因此,从上面的步骤1和步骤2,更新顶点的所有相邻顶点的时间复杂度是E*(logV).或E*logV.
4. 因此,所有V顶点的时间复杂度是V*(E*logV),即O(VElogV).

但是Dijkstra算法的时间复杂度是O(ElogV).为什么？