相关疑难解决方法(0)

我认为这个问题有一个简单的解决方案,几个for循环和一些花哨的计数器,但显然它更复杂.

所以我的问题是,你如何编写(在C中)对角线条中方形矩阵的函数遍历.

例:

1  2  3
4  5  6
7  8  9

必须按以下顺序遍历:

[1],[2,4],[3,5,7],[6,8],[9]

上面的每个条带都用方括号括起来.其中一个要求是能够区分条带.这意味着你知道什么时候开始新的条带.这是因为我必须为条带中的每个项目调用另一个函数,然后在新条带的开头之前调用.因此,没有代码重复的解决方案是理想的.

    int func(int n){
       if(n==1)
         return 0;
       else
         return sqrt(n);
    }

其中sqrt(n)是C math.h库函数.

1. O(1)
2. O(lg n)
3. O(lg lg n)
4. 上)

我认为运行时间完全取决于sqrt(n).但是,我不知道这个功能是如何实际实现的.

PS找到我所知道的数字的平方根的一般方法是使用牛顿方法.如果我没有错,使用牛顿方法的时间复杂度变为O(lg n).答案应该是O(lg n)吗？

PPS在我最近出现的测试中得到了这个问题.