时间戳

首页 > 解决方案 > 函数增长的近似值

algorithm - 函数增长的近似值

问题描述

我正在尝试学习算法分析，但我发现运行时间有点难以理解。我有一个问题，我应该找到函数增长的精确近似值和大 O 表示法。

我想知道D的增长顺序是否为N，因为函数D最多只执行n次step（）？

我有这个功能

void step() {
        count++;
    }
void functionD(int n) {
        if (n % 2 == 0) {
            step();
        }
        else
            step();
    }

标签： algorithmbig-o

解决方案

看来你打错了，因为你的要求

因为functionD只step()在大多数 n时候执行？

听起来很奇怪。看看就好。两个 if分支都做同样的事情：

void functionD(int n) {
    if (n % 2 == 0) {  // either n is even 
        step();        //   ... do the step()
    }                  
    else               // or n is odd
        step();        //   ... do exactly the same - step()
}

所以我们可以将代码简化为

void functionD(int n) {
    // either n is even or odd do the step; 
    step();
}

现在，因为step除了增加一个conter

void step() {
    count++;
}

functionD增加 acounter就是这样：

void functionD(int n) {
    count++;
}

最后，我们有 for functionD: ignore n, increment a counter，这个操作有明显的O(1)时间复杂度（functionD ignores n）。

推荐阅读