带if语句的嵌套循环的时间复杂度 [英] Time complexity of nested loops with if statement

问题描述

我正在使用高级C ++上一堂课，但是我试图找到锁定在if语句后面的嵌套for循环的Big-Θ感到困惑.不幸的是，我的教授(出于某种奇怪的原因)只是希望我们从预备课上知道这一点(即使我是在另一所课程内容不同的学院就读的)，也不会花时间教我.

I am taking a class on advanced C++ but I am getting stumped trying to find the Big-Θ of nested for-loops that are locked behind if-statements. Unfortunately my professor (for some strange reason) just expects us to know this from a pre-req class (even though I took it at a different college with different course content) and will not take the time to teach me.

我不想让任何人为我解决家庭作业，并且我确实想学习这些概念，因此我在下面创建了自己的独特功能.考虑到第二个循环只运行几次，我只是无法确定这种类型的函数是Θ(n)还是Θ(n ^ 2).我们将不胜感激任何一般性的解释，或者可能向正确的方向指出如何解决这些类型的问题:)

I don't want anyone to solve my homework for me and I genuinely want to learn the concepts, so I created my own unique function down below. I just cannot wrap my head around whether this type of function is Θ(n) or Θ(n^2) given that the second loop only runs a few times. Any general explanation or maybe pointers in the right direction of how I can figure these types of problems out would be greatly appreciated :)

注意:假定变量n是任意大小的正整数.

Note: Assume the variable n is a positive integer of any size.

int count = 20;
for (int i = 0; i < n; i ++) {
    if (i == count) {
        for (int j = 0; j < count; j++) {
            // Some O(1) code
            // Maybe a print to console or something
        }
        count *= 2;
    }
}

推荐答案

您需要问的第一个问题是，您在数什么?通常，您可以找到一些不错的东西来计数，而不仅仅是指令"，以得到很好的猜测.拥有big-O值后，可以再次检查该值是否正确.

The first question you need to ask is, what are you counting? Usually you can find some decent thing to count, instead of just "instructions", to get a good guess. Once you have your big-O value, you can double check the value is right.

int count = 20;
for (int i = 0; i < n; i ++) {

好吧，这显然要运行O(n)次.

Ok, this obviously runs O(n) times.

    if (i == count) {

在第一次通过时，输入O(n/20)次.这可能会改变.

On a first pass, this is entered O(n/20) times. This may change.

        for (int j = 0; j < count; j++) {

这将运行O(count)次.

This runs O(count) times.

            // Some O(1) code
            // Maybe a print to console or something
        }

        count *= 2;

现在，这变得很有趣.每次计数加倍.

now this gets interesting. Each time count doubles.

因此，第一个内循环在20个外循环之后运行，然后执行20 O(1).

So the first inner loop runs after 20 outer loops, and then does 20 O(1) work.

计数加倍.第二个内部循环在40个外部循环之后运行，并且执行40 O(1).

Count doubles. The second inner loop runs after 40 outer loops, and does 40 O(1) work.

计数加倍.第三个内部循环在80个外部循环之后运行，并执行80 O(1).

Count doubles. The third inner loop runs after 80 outer loops, and does 80 O(1) work.

计数加倍.第四个内部循环在160个外部循环之后运行，并在内部循环中执行160 O(1).

Count doubles. The forth inner loop runs after 160 outer loops, and does 160 O(1) work in the inner loop.

现在您必须将其转换为数学.您可以猜测，然后检查.但是，假设您无法猜测?

Now you have to turn this into math. You could guess, then check. But suppose you can't guess?

好吧，画出来！

 n   |    inner steps
------+----------------
  20  |    20
  40  |    20+40 = 60
  80  |    20+40+80 = 140
 160  |    20+40+80+160 = 300
 320  |    20+40+80+160+320 = 620

将其扔到制图程序上.该图是什么样的?如果曲线弯曲，则取对数可能会给您带来斜率，从中可以找到多项式的指数.

toss that on a graphing program. What does the graph look like? If it curves, taking the logarithm might give you slope from which you can find the exponential of a polynomial.

请记住使用散点图.您根本不在乎60、100或240会发生什么.您关心的是峰值，峰值出现在20处，并且每增加一倍.散点图会使您的图形化点下降.

Remember to use a scatter plot. You don't care what happens at 60, 100, or 240 all that much. You care about the peaks, which happen at 20 and every doubling. A scatter plot drops your graphed points way down.

还要计算外循环步数和与计数的比较，以确保步幅不大.

Also count the outer loop steps and the comparisons with count to ensure they aren't huge.

一旦有了假设，就应设法证明答案正确.

Once you have a hypothesis, work out how to prove your answer right.

这篇关于带if语句的嵌套循环的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！