带有随机对象的while循环的java大O时间复杂性
public class Question2 {
//running time of function is N!!!!!!
public static boolean isThere(int[] array, int num, int index){
boolean isItThere = false; //running time of 1
for(int i =0; i <= index; i++){ //running time i
if(array[i] == num){ //running time of 1
isItThere = true; //running time of 1
}
}
return isItThere;
}
public static int[] firstAlgo(int N){
Random random = new Random(); //running time of 1(initilizing)k
int[] arr = new int[N];
for (int i = 0; i < N; i++){
int temp = random.nextInt(N+1); //running time of random is O(1)
while (isThere(arr, temp, i)){
temp = random.nextInt(N+1);
}
arr[i] = temp;
}
return arr;
}
}
我想计算while循环的时间复杂度,我知道isThere函数的运行时间是N,firstAlgo中的main for循环也是如此
# 1 楼答案
你可以凭经验来做。只需运行代码并计时,使用不同的值N。我这样做了,复杂性似乎是O(N^2)。我做了一系列的测试,每一次都是N的翻倍,而时间似乎从未从大约翻两番的水平上后退过。我厌倦了在N=256000时等待,这大约需要20万毫秒
如果你想走这条路,你会想做更多的运行更仔细的分析。你可以设置一个外部循环来持续进行批量测试,比如说每级10次,对它们进行计时,然后将N加倍,然后再次进行测试。。。记录所有的时间。你可以在一夜之间运行测试,并从经验上对行为有一个相当清晰的认识
如果这不是你想要的方式,至少可以是一种反复检查你答案的方式
# 2 楼答案
简短版本:
这是一个曲线图,将所做的经验工作量与我得到的形式为N2logn的函数的最佳拟合近似值进行比较,其为(N2ln)/1.06:
好奇?继续读下去。:-)
让我们从这里的代码中退一步,看看实际的逻辑在做什么。代码的工作原理如下:对于数组的每个前缀0、1、2、3。。。,N、 该代码连续生成0到N之间的随机数,直到生成一个以前从未见过的随机数。然后,它将该数字写在当前阵列插槽中,并转到下一个插槽
我们在分析中需要的一些观察结果。假设我们即将进入
firstAlgo
中循环的第k次迭代。关于阵列的前k个插槽的元素,我们可以说些什么?那么我们知道以下几点:现在,我们可以开始数学了。让我们看看
firstAlgo
中循环的迭代k。每次生成一个随机数时,我们都会查看(k+1)数组插槽,以确保该数字不会出现在那里。(顺便说一句,我将使用这个数量作为所做总功的代理,因为大部分能量将用于扫描该阵列。)所以,我们需要问一下,在我们找到一个唯一的数字之前,我们将产生多少个数字以上列表中的事实(3)在这里很有用。它说在迭代k中,数组中的第一个k+1插槽彼此不同,我们需要生成一个不同于所有这些插槽的数字。我们可以选择N+1个随机数选项,因此我们可以选择(N+1)-(k+1)=N-k个选项来选择那些不曾使用过的随机数。这意味着我们选择一个尚未出现的数字的概率是(N-k)/(N+1)
快速检查以确保这个公式是正确的:当k=0时,我们可以生成除0以外的任意随机数。有N+1个选择,所以我们这样做的概率是N/(N+1)。这符合我们上面的公式。当k=N-1时,所有前面的数组元素都是不同的,我们只能选择一个数字。这意味着我们的成功概率为1/(N+1),同样符合我们的公式。酷
概率论中有一个有用的事实,如果你一直在抛一个概率为p的有偏硬币,那么在你抛硬币之前,预期的抛硬币次数是1/p。(更正式地说,that's the mean of a geometric random variable with success probability p,你可以用期望值的形式定义和一些泰勒级数来证明这一点。)这意味着在该循环的第k次迭代中,在得到唯一的随机数之前,我们需要生成的预期随机数是(N+1)/(N-k)
总的来说,这意味着在
firstAlgo
中循环的迭代k上完成的预期工作量由(N+1)(k+1)/(N-k)给出。那是因为然后,我们可以通过将k=0和N-1相加得到所完成的总功。这给了我们
现在,“所有”我们要做的就是简化这个求和,看看我们得到了什么。:-)
让我们从分解公共(N+1)项开始,返回
忽略(N+1)项,我们剩下的任务是简化求和
现在,我们如何评估这个总和?这里有一个有用的事实。总数
返回Nth harmonic number(表示为HN)和isΘ(logn)。不仅仅是Θ(logn),它非常非常接近ln
考虑到这一点,我们可以进行以下重写:
这里的基本思想是将(k+1)/N视为分数1/N的(k+1)个副本,然后像这样将它们重新组合成单独的行
一旦我们这样做了,请注意,最上面一行是第n个谐波数Hn,下面一项是第(n-1)个谐波数Hn-1,下面一项是第(n-2)个谐波数Hn-2,以此类推。这意味着我们的分数和等于
将其乘以我们之前提取的原始因子N,我们得到的总体运行时间是Θ(N2logn)
那么,这在实践中成立吗?为了找出答案,我在一系列输入上运行了代码,并计算了
isThere
中循环的平均迭代次数。然后,我将每个项除以logn,并进行多项式拟合回归,以查看余数与Θ的匹配程度(N2)。回归发现,最佳多项式图的多项式项为N2.01,强烈支持这一点(在对数N项相乘后),我们看到的是N2logn(注意,运行相同的回归,但不首先划分对数N项,显示N2.15,这清楚地表明这里正在发生N2以外的事情。)使用预测的方程(N)=(N2ln)/1.06,用经验确定的最后一个常数,我们得到上面的图,这几乎是一个完美的匹配
现在,快速结束这个问题。回想起来,我本应该预测运行时几乎是立即发生的(N2logn)。原因是这个问题与coupon collector's problem密切相关,这是一个经典的概率难题。在这个谜题中,有N个不同的优惠券要收集,你一直随机收集优惠券。问题是,在期望中,你需要收集多少张优惠券,然后才能获得一份
这与我们在这里遇到的问题非常吻合,在每一步中,我们都从一袋N+1选项中选择,并试图最终选择所有选项。这意味着我们需要在所有迭代中进行Θ(logn)随机绘制。然而,每次绘制的成本取决于我们所处的循环迭代,后期绘制的成本高于早期绘制的成本。基于大多数绘图都在后半部分的假设,我应该能够猜到,我们平均每绘图做Θ(N)个工作,然后乘以该值得到Θ(N2logn)。但是,我只是从零开始重新驱动。哎呀
唷,那真是一次旅行!希望这有帮助
# 3 楼答案
记住,Big-O是最坏的行为。正如其中一条评论中提到的,这有可能永远不会终止,从而导致无限大的O,因为这段代码是不确定的
对于一个平均情况,random做了预期的事情。您正在查看isThere函数的O(N)。对于最后一次查找值的迭代,您将平均N次操作。在这一点上,你达到了O(N^2)。最后,您需要重复此操作N次以填充数组,这将导致O(N^3)