标签: complexity-theory

您创建或看到的最复杂/最复杂的网站或网页是什么？

是什么让它如此复杂或复杂？

import string,random,platform,os,sys
def rPass():
    sent =  os.urandom(random.randrange(900,7899))
    print sent,"\n"
    intsent=0
    for i in sent:
        intsent += ord(i)
    print intsent
    intset=0
rPass()

我需要帮助确定该算法的字节码部分的总可能输出.不要担心for循环和用于下线的ord东西. - 新手加密的家伙.

我不确定这是否是我理解的问题但是Big Oh符号的这个方面对我来说似乎很奇怪.假设您有两种算法 - 第一次预制n ^ 2次操作,第二次执行n ^ 2-n次操作.由于二次项的优势,两种算法都具有复杂度O(n ^ 2),但第二种算法总是优于第一种算法.这对我来说似乎很奇怪,Big Oh符号使它看起来像是一样的.我不知道...

我有这个代码,想知道它的时间复杂度:

    int N,M; // let N and M be any two numbers 
    while(N != M && N > 0 && M > 0){
       if(N > M)N -= M;
       else M -= N;
    }

我不知道如何分析这个,因为M和N的值以不寻常的方式减少.有没有一种标准的方法来解决这个问题？

我不得不确定这段代码的大O复杂性.我认为答案是nlogn,但显然是n.任何人都可以帮助解释为什么会这样吗？

void funct(int n)
{
    for (int i = n; i > 0; i /= 2)
        for(int j = 0; j < i; j++)
            printf("%d\n", j%2);
}

对于给定的余额和利率,我的计划计算一年内偿还债务的最低月付款.然而,一个平均计算在~0.000150s,另一个计算在~0.000300s.这是否意味着不同程度的渐近复杂性？

这些是代码示例:

较慢的一个:

import time
start_time = time.time()

balance = 999999
annualInterestRate = 0.18
mRate = annualInterestRate/12
high = (((mRate+1)**12)*balance)/12
low = balance/12
guessed = False

def balanceLeft(balance,mRate,minPayment):
    monthsLeft = 12
    while monthsLeft > 0:
        unpaidBalance =  balance - minPayment
        interest = mRate * unpaidBalance
        balance = unpaidBalance
        balance += interest
        monthsLeft -= 1
    return balance

while guessed == False:
    minPayment = (high + low) / 2
    if round(balanceLeft(balance,mRate,minPayment),2) < 0:
        high = minPayment
    elif round(balanceLeft(balance,mRate,minPayment),2)> 0:
        low = minPayment …

public int Loop(int[] array1) {
        int result = 0;
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array1.length; j++) {
                for (int k = 1; k < array1.length; k = k * 2) {
                    result += j * j * array1[k] + array1[i] + array1[j];
                }
            }
        }
        return result;
    }

我试图找到复杂度函数来计算这里的算术运算次数.我知道复杂性类是O(n ^ 3),但是我在计算步骤时遇到了一些麻烦.

到目前为止,我的理由是我计算算术运算的数量是8,那么复杂度函数是8n ^ 3吗？

非常感谢任何正确方向的指导,谢谢!

假设方法m1和m2是静态void,并通过处理Object []类型的参数来计算相同的结果.根据经验,我们发现m1 - > T(N)= 100N且m2 - > T(N)= 10Nlog2N,其中时间以微秒为单位.对于什么尺寸的输入,使用m1和m2更好？所以我会使用m1作为大数字,而我会使用m2作为小数字吗？只是检查答案.

我无法想象如何构建这样的算法.

算法"对于N个元素的每个排列,蛮力推动旅行商问题,其中边缘由元素的顺序决定"具有这样的复杂性吗？

我是否正确地说大O符号的时间复杂度只是O(1)？

public boolean size() {
        return (size == 0);
    }