标签: asymptotic-complexity

该方法hasTwoTrueValues返回true,如果在阵列的至少两个值boolean是true.为所提出的所有三种实现提供Big-O运行时间.

// 版本1

public boolean hasTwoTrueValues(boolean[] arr) {
    int count = 0;
    for(int i = 0; i < arr.length; i++)
        if(arr[i])
            count++;
        return count >= 2;
}

// 第2版

public boolean hasTwoTrueValues(boolean[] arr) {
    for(int i = 0; i < arr.length; i++)
        for(int j = i + 1; j < arr.length; j++ )
            if(arr[i] && arr[j])
                return true;
}

// 第3版

public boolean hasTwoTrueValues(boolean[] arr) {
    for(int i = 0; i < …

我想计算这个嵌套for循环的θ复杂度:

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < j; k++) {
                // statement

我会说它是n ^ 3,但我不认为这是正确的,因为每个for循环不会从1变为n.我做了一些测试:

n = 5 - > 10

10 - > 120

30 - > 4060

50 - > 19600

所以它必须在n ^ 2和n ^ 3之间.我尝试了总和公式等,但我的结果太高了.虽然n ^ 2 log(n),但那也错了......

任何人都可以指向一个资源,列出基本的clojure库函数的Big-O复杂性,如conj,cons等等？我知道Big-O会根据输入的类型而有所不同,但是,这样的资源是否可用？我对编写某些东西感到不舒服,却没有大致了解它的运行速度.

关于螺纹二进制搜索树的解释(如果你知道它们,请跳过它):

我们知道在具有n个节点的二叉搜索树中,有n + 1个左右指针包含null.为了使用包含null的内存,我们按如下方式更改二叉树 -

对于树中的每个节点z:

如果left [z] = NULL,我们在left [z]中输入tree-predecessor(z)的值(即指向包含前任键的节点的指针),

如果right [z] = NULL,我们在右[z]中输入tree-successor(z)的值(同样,这是指向包含后继键的节点的指针).

像这样的树称为线程二进制搜索树,新链接称为线程.

我的问题是: 螺纹二进制搜索树的主要优点是什么(与"常规"二叉搜索树相比).在网上快速搜索告诉我,迭代地实现有序遍历有助于,而不是递归地实现.

这是唯一的区别吗？还有其他方法可以使用线程吗？

这是如此有意义的优势吗？如果是这样,为什么？递归遍历也花费O(n)时间,所以..

非常感谢你.

如何找到 n choose floor(n/2) 的渐近增长？我尝试使用扩展并得到它等于

[n*(n-1)*........*(floor(n/2)+1)] / (n-floor(n/2))!

知道我怎么去那里吗？任何帮助表示赞赏，更喜欢提示而不是答案

感谢您的帮助

words = [....#Big list of words]
words_set = set(words)

当 n=len(words) 时，我很难确定 set(words) 的复杂性是多少。是 O(n) 因为它在列表的所有项目上移动，还是 O(l(nl)) 当 l 是单个单词长度时？感谢帮助！如果WC和BC之间也有区别的话。

编辑：不要介意 O(l(nl)) ，重复子串大 O 是错误的。

我很沮丧.

在CLRS第3版,第95页(第4.5章)中,它提到了像

T(n) = 2T(n/2) + n lg n

无法用大师定理解决因为差异

f(n)/n^(log_b(a)) = (n lg n)/n^1 = lg n

不是多项式.

但后来我遇到喜欢的网页这样这个地方,在页面的底部,它提到的完全一样的复发和说,它是能够与主定理,因为它属于一种"扩展的情况下2"来解决,即使不同的是非多项式.它变为n lg^2 n(将对数因子f(n)加1).

然后,我遇到类似的网页这其中,例如,在(E)好像扩展案例2(复发是明确的应用T(n) = 4T(n/2) + n^2 lg n),但随后的解决方案是不是n^2 log^2 n,而是n^2 log n!我错了还是纸张错了？

任何人都可以清理矛盾,并清楚地说明何时可以使用主定理,何时不能使用？什么时候多项式差异检查很重要,什么时候不重要？扩展案例2是否可用,或实际上是否违反了某些内容？

编辑:

我尝试直接从第二篇论文解决复发(e),我得到:

T(n) = n^2 lg^2(n)/2 + n^2 lg(n)/2

这不是大the n^2 lg^2 n？

我知道如何找到几乎所有选项（简单函数、带循环的函数等）的时间复杂度，但我无法弄清楚如何确定调用另一个函数的函数的时间复杂度，特别是如果调用函数是在一个循环内。

我写了一些函数，用作示例。

int g(int k) {
  int i=0;

  while(k>0) {
    i += k;
    k= k/2;
  }

  return i;
}

int f(int n) {
  int m = 0;

  for (int i=0; i<n; ++i) {
    for (int j=i; j<n; ++j) {
      m += g(j);
    }
  }

  return m;
}

我想不通：我是否必须考虑 function 的时间复杂度g()，以及如果我必须如何在 function 中计算它f()？或者我只是忽略函数g()而只包含函数中的函数调用f()？

我正在寻找一些用于编码访谈的在线算法解决方案,我不明白为什么这个算法声称是O(n ^ 3).

警告:我理解工业中滥用了大哦符号,当我提到O(n)时,我使用这种符号来表示算法运行时的上限,这在大多数地方学术界都是常见的.

寻找最长的回文子串.一个简单的解决方案可能是

bool isPalindrome(std::string s) {
  if (s.length() <= 1) {
    return true;
  }

  if (s[0] == s[s.length() - 1]) {
    return isPalindrome(s.substr(1, s.length() - 2));
  } else {
    return false;
  }
}

std::string longestPalindrome(std::string s) {
  std::string max_pal = "";
  for (size_t i = 0; i < s.length(); ++i) {
    for (size_t len = 1; len <= s.length() - i; ++len) {
      std::string sub = s.substr(i,len);
      if (isPalindrome(sub)) {
        if (max_pal.size() < sub.size()) max_pal = sub; …

例如，ArrayListJava中的s的大小调整系数为2。当ArrayList包裹的数组空间不足时，该数组的所有元素都将转移到新数组，该数组的大小是原始数组的2倍。

由于Python列表/数组自然是动态的，因此它们的大小调整因素是什么？还是他们使用其他缩放方法？如果是这样，那是什么方法？它的渐近运行时是什么（大O）？