标签: complexity-theory

我相信大多数人都知道,如果函数输入大小为n,嵌套循环的复杂度为O(n ^ 2)

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

我认为这是类似的,通过一个类似的论点,但我不确定任何人都可以确认？

for(int i = 0, max = n*n; i < max; i++{
...
}

如果是这样,我猜有些类型的代码,除了递归和子程序之外,其大O映射并不是很明显.

如果数据结构具有随机访问,则标准表示std::binary_search(...)该两个相关函数std::lower_bound(...)和std::upper_bound(...)O(log n).因此,鉴于此,我假设这些算法具有O(log n)性能std::deque(假设其内容由用户保持排序).

然而,似乎内部表示std::deque是棘手的(它被分成块),所以我想知道:O(log n)搜索的要求是否成立std::deque.

因此,查找列表中的最大元素需要O(n)时间复杂度(如果列表具有n个元素).我试图实现一个看起来更快的算法.

(define (clever-max lst)
  (define (odd-half a-list)
    (cond ((null? a-list) (list))
          ((null? (cdr a-list))
           (cons (car a-list) (list)))
          (else
           (cons (car a-list)
                 (odd-half (cdr (cdr a-list)))))))
  (define (even-half a-list)
    (if (null? a-list)
        (list)
        (odd-half (cdr a-list))))
  (cond ((null? lst) (error "no elements in list!"))
        ((null? (cdr lst)) (car lst))
        (else
         (let ((l1 (even-half lst))
               (l2 (odd-half lst)))
           (max (clever-max l1) (clever-max l2))))))

这实际上更快吗？!你会说渐近时间复杂度是什么(紧束缚)？

我有一个对象列表objectList,其中每个对象都有几个属性,其中一个是myUniqueNo.myUniqueNo是每个对象的随机整数.比方说我有一个整数n.我确信在objectList肯定有一个具有myUniqueNoas 的对象n.我想返回具有'myUniqueNo'的对象n.是否有任何O(1)算法或Java中的方法返回此对象？

这个算法的时间复杂度是多少:

sum = 0
i = 1

while (i < n) {

    for j = 1 to i {
        sum = sum + 1
    }

    i = i*2;
}

return sum

我知道while循环是O(logn),但循环的复杂性是for什么？难道O(n)还是O(logn)？

我在java中计算了这个算法的最佳案例复杂度,平均值和最差值,我认为如果O (1)在最坏的情况下是好的O (n),但我不知道是否平均!你能帮我解决一下吗？谢谢!

public boolean searchFalse(boolean[] b){ 
 boolean trovato=false; 
  for(int i=0;i<b.length;i++){
   if(b[i]==false){
 trovato=true;
 break;
   }
  }return trovato;
}

请考虑以下方法:

def fun(lst) : 
    concat = "".join(lst) 
    return hash(concat) 

这段代码的地方复杂性是多少？
谢谢!

考虑以下两个累积和(cumsum)函数:

cumsum :: Num a => [a] -> [a]
cumsum [] = []
cumsum [x] = [x]
cumsum (x:y:ys) = x : (cumsum $ (x+y) : ys)

和

cumsum' :: Num a => [a] -> [a]
cumsum' x = [sum $ take k x | k <- [1..length x]]

当然,我更喜欢的定义cumsum到的cumsum',我知道,前者具有线性复杂度.

但为什么cumsum'还有线性复杂性呢？take本身具有线性复杂性在其参数的长度和k从运行1到length x.因此,我预计二次复杂度为 cumsum'.

而且,常数cumsum'低于cumsum.这是由于后者的递归列表附加吗？

注意:欢迎任何累积金额的明智定义.

编辑:我正在测量执行时间(:set +s …

public static void complexityexample(int n) {
    int count = 0;
    int k = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            count++;
        }
        k *= 2;
        for (int t = 0; t < n; t++) {
            count++;
        }
        System.out.println(count);
    }
}

有人能给我答案吗？

例如,我知道for循环中的nuber操作是2N + 2,

和count ++中的操作数; 是N.

但是对于其他部分呢.

在一个用于分析算法的类中,我们为Kruskal算法提供了这个伪代码:

然后他说明了以下不相交的森林:

m个MAKE-SET,UNION和FIND-SET操作的序列,其中n个是MAKE-SET操作,可以在不相交的森林上执行,在最坏情况下的时间O( mα)中通过秩和路径压缩进行并联(n)).

用于计算步骤2和步骤5-8的复杂性

对于连接的G:| E | ≥| V | -1; m = O(V + E),n = O(V);

所以步骤2,5-8:O((V + E)α(V))= O(Eα(V))

α(V)= O(lg V)= O(lg E); 所以我们得到O(E lg E)----- //这里α(V)如何相等？

Kruskal:步骤3,5-8和步骤4:O(E lg E)

观察:| E | <| V | 2 - > lg E = O(lg V)

所以,Kruskal的复杂性:O(E lg V)

我试图理解这个"alpha(n)"/"α(n)"函数背后的逻辑,从我所读到的看来,简单地说,Ackermann函数是指数速度快得令人难以置信的,而且逆是以对数方式非常缓慢地增长.

如果我的解释是正确的,"α(n)"代表什么？这是否意味着MAKE-SET操作最多为O(lg n)？如何/为什么使用逆阿克曼是必要的？我的印象是这个操作执行V次(对于每个顶点).在此之后,α(V)也被简化为O(lg V)= O(lg E),这是否意味着,在最大值时,α(V)可以由O(lg V)表示.

另外,为什么是| E | <| V | ^ 2 - > lg E = O(lg V) …