标签: time-complexity

树遍历的时间复杂度是多少,我敢肯定它一定是显而易见的,但是我的可怜的大脑现在无法解决这个问题.

我想出了这种矩阵乘法算法.我在某处读到矩阵乘法的时间复杂度为o(n ^ 2).但我认为我的算法会给出o(n ^ 3).我不知道如何计算嵌套循环的时间复杂度.所以请纠正我.

for i=1 to n
   for j=1 to n    
     c[i][j]=0
     for k=1 to n
         c[i][j] = c[i][j]+a[i][k]*b[k][j]

我阅读了http://swtch.com/~rsc/regexp/regexp1.html,其中作者说,为了在正则表达式中进行反向引用,在匹配时需要回溯,这使得最坏情况的复杂度呈指数级增长.但我并不确切地知道为什么反向引用会引入回溯的必要性.有人可以解释为什么,也许提供一个例子(正则表达式和输入)？

什么是迭代std::set/ std::multiset/ std::map/ 的时间复杂度std::multimap？我相信它在集合/地图的大小上是线性的,但不是那么肯定.是否在语言标准中指定？

是O(log(log(n)))实际上只是O(log(n))当谈到时间复杂度？
你是否同意这个函数g()的时间复杂度O(log(log(n)))？

int f(int n) {
    if (n <= 1)
        return 0;
    return f(n/2) + 1;
}

int g(int n) {
    int m = f(f(n));
    int i;
    int x = 0;
    for (i = 0; i < m; i++) {
        x += i * i;
    }
    return m;
}

在 dict.items() 中检查成员资格的时间复杂度是多少？

根据文档：

键视图是类似设置的，因为它们的条目是唯一且可散列的。 如果所有值都是可散列的，因此 (key, value) 对是唯一且可 散列的，那么项目视图也是类似集合的。（值视图不被视为类集合，因为条目通常不是唯一的。）对于类集合视图，为抽象基类 collections.abc.Set 定义的所有操作都可用（例如，==、< , 或 ^)。

所以我用下面的代码做了一些测试：

from timeit import timeit

def membership(val, container):
    val in container

r = range(100000)
s = set(r)
d = dict.fromkeys(r, 1)
d2 = {k: [1] for k in r}
items_list = list(d2.items())

print('set'.ljust(12), end='')
print(timeit(lambda: membership(-1, s), number=1000))
print('dict'.ljust(12), end='')
print(timeit(lambda: membership(-1, d), number=1000))
print('d_keys'.ljust(12), end='')
print(timeit(lambda: membership(-1, d.keys()), number=1000))
print('d_values'.ljust(12), end='')
print(timeit(lambda: membership(-1, d.values()), number=1000))
print('\n*With hashable dict.values')
print('d_items'.ljust(12), end='')
print(timeit(lambda: …

任何人都可以解释以下Dictionary方法的复杂性是什么？

ContainsKey(key)
Add(key,value);

我想弄清楚我写的方法的复杂性:

public void DistinctWords(String s)
{
    Dictionary<string,string> d = new Dictionary<string,string>();
    String[] splitted = s.split(" ");
    foreach ( String ss in splitted)
    { 
        if (!d.containskey(ss))
            d.add(ss,null);
    } 
}

我假设2个字典方法具有log(n)复杂度,其中n是字典中的键数.它是否正确？

我可以看到,当在BST中查找值时,每次我们将节点与我们要查找的值进行比较时,我们会将树的一半留下.

但是,我不明白时间复杂性的原因O(log(n)).所以,我的问题是:

如果我们有一个N元素的树,为什么查找树并检查特定值是否存在的时间复杂度为O(log(n)),我们如何得到它？

我试图回答这个问题,只使用递归(动态编程) http://en.wikipedia.org/wiki/Longest_increasing_subsequence

从文章和SO周围,我意识到最有效的现有解决方案是O(nlgn).我的解决方案是O(N),我找不到它失败的情况.我包括我使用的单元测试用例.

import static org.junit.Assert.assertEquals;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

public class LongestIncreasingSubseq {

    public static void main(String[] args) {
        int[] arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, 1};
        getLongestSubSeq(arr);
    }

    public static List<Integer> getLongestSubSeq(int[] arr) {
        List<Integer> indices = longestRecursive(arr, 0, arr.length-1);
        List<Integer> result = new ArrayList<>();
        for (Integer i : indices) {
            result.add(arr[i]);
        }

        System.out.println(result.toString());
        return result;
    }

    private static List<Integer> longestRecursive(int[] arr, …

我为旅行商问题编写了一个强力搜索算法,并对其进行了测试,以查看各种"城市"所需的时间.从下面的图中,我们可以看到,时间大约是成正比的(n-1)!地方n是"城市"的数量.它与n!(毕竟(n-1)! = n! / n)不成正比.

我的问题是,说算法运行是否仍然正确O(n!),或者说我更好O((n-1)!)吗？我以前从未见过后者,但似乎更准确.看来我在这里误解了一些东西.

[t =所用时间,n =城市数量]