标签: time-complexity

假设我们有一个问题，某个算法（我们称之为算法_1）的时间复杂度为 ，O(n^2)另一个算法（我们称之为算法_2）的时间复杂度为O(n)，但实际上我们看到n < 1000算法_1 更快，否则算法_2 更快是比较快的。

为什么我们不能直接写这样的代码：

if ( n < 1000)
  do algorithm_1
else
  do algorithm_2

这是程序员真正做的事情还是有缺点？

对于较小的程序，这似乎是一个好主意。

鉴于此排序算法,您如何表达其时间复杂度？

最初在这里介绍 (部分档案).

#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

example usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7

密钥集合(Set,Map,WeakSet和WeakMap)的ES6规范提供了什么时间复杂度(以大O表示法)？

我的期望,并且我希望大多数开发人员都希望,规范和实现将使用广泛接受的性能算法,在这种情况下Set.prototype.has,add并且delete在一般情况下都是O(1).相同的Map和Weak–等价物.

对于我来说,实现的时间复杂性是否是强制性的,例如在ECMAScript 2015语言规范 - 第6版 - 23.2设置对象中,这一点并不完全清楚.

除非我误解它(我当然很可能),看起来ECMA规范要求实现(例如Set.prototype.has)使用线性时间(O(n))算法.令我非常惊讶的是,规范中不会强制要求甚至不允许使用更高性能的算法,我会对为什么会出现这种情况的解释非常感兴趣.

是ArrayListjava中的数组还是列表？get操作的时间复杂度是什么,是O(n)或者O(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),它也需要更长的时间.有人可以扩展吗？我提出它是因为我经常看到算法,例如,他们将首先执行排序步骤或类似的事情,并且在确定总复杂度时,它只是限制算法的最复杂元素.

为什么我一直在哈希表上看到这些函数的不同运行时复杂性？

在wiki上,搜索和删除是O(n)(我认为哈希表的要点是持续查找,所以如果搜索是O(n)则重点是什么).

在不久前的一些课程笔记中,我看到了很多复杂性,具体取决于某些细节,包括所有O(1).如果我可以获得所有O(1),为什么要使用任何其他实现？

如果我在C++或Java等语言中使用标准哈希表,那么我可以期待时间复杂度是多少？

我想比较2个字符串并保持匹配,在比较失败的地方分开.

所以,如果我有2个字符串 -

string1 = apples
string2 = appleses

answer = apples

另一个例子,因为字符串可能有多个单词.

string1 = apple pie available
string2 = apple pies

answer = apple pie

我确信有一种简单的Python方法可以做到这一点,但我无法解决,任何帮助和解释都表示赞赏.

我在算法设计中有一个关于复杂性的问题.在这个问题中给出了一段代码,我应该计算这段代码的复杂性.伪代码是:

for(i=1;i<=n;i++){
    j=i
    do{
        k=j;
        j = j / 2;
    }while(k is even);
}

我为一些数字尝试了这个算法.我得到了不同的结果.例如,如果n = 6,则该算法输出如下所示

i = 1 -> executes 1 time
i = 2 -> executes 2 times
i = 3 -> executes 1 time
i = 4 -> executes 3 times
i = 5 -> executes 1 time
i = 6 -> executes 2 times

它没有常规主题,我该如何计算呢？

我知道这个算法的大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)快。为什么是这样？