我怎么知道这个函数是否在时间 O(N) 和内存 O(N) 内工作？

Question

任务是：

Given is an array containing N numbers, A[0],A[1],...A[N-1]. Compute the array B of length N, such that B[i]=A[0]*A[1]*...A[i-1]*A[i+1]...*A[N-1]. You shouldn't use division and both time and memory complexity should be O(N).

#include <iostream>
#include <math.h>
#include <conio.h>
#include <time.h>

long int find_solution(int result, int multiplier, int increment)
{
    int safety=1;
    long int solution=0;
    while(safety==1)
    {
        if (solution*multiplier==result)
        {
            safety=0;
            return solution;    
        }
        else if((solution+increment)*multiplier>result)
        {
            safety=0;
            return find_solution(result,multiplier, increment*0.1);
        }
        solution=solution+increment;
    }
}

int main()
{
    double time_spent=0.0;
    int A[20] = {2, 3, 4, 5, 6,1,2,3,4,5,1,1,1,2,3,1,1,1,1,1};
    clock_t begin=clock();
    int i;
    long int main_result=1;
    for(i=0;i<20;i++)
    {
        main_result=main_result*A[i];
    }
    printf("\n%d\n",main_result);
    long int B[20];
    for(i=0;i<20;i++)
    {
        B[i]=find_solution(main_result, A[i],100000000);
    }
    for(i=0;i<20;i++)
    {
        printf("%d\n",B[i]);
    }
    clock_t end=clock();
    time_spent=(double)(end-begin)/CLOCKS_PER_SEC;
    printf("Time elapsed: %.20f\n",time_spent);
    getch();
    return 0;
}

这个函数我自己分析了一下，好像还可以。我在电脑上计算时间的时候，如果输入5,10,15就好了（我每个输入量做了21个小节）。当它是 20 时，时间开始增长，超过它可能应该增长的速度。

5-0.01333333
10-0.02276
15-0.03757
20-0.07066

可能是什么原因？我没有使用任何嵌套循环。我的功能可以吗？

Answer 1

O(N) 意味着该算法应该进行 N 次操作，在您的情况下，它受限于 A 的输入数组大小。

在 main 函数中，循环迭代了 20 次，但在“find_solution”方法循环中，复杂度重复。

我觉得你有点困惑，你的任务只需要将 A 的每一项乘以所有 B，无论 B 的 i 是什么：

B[i]=A[0]A[1]...A[i-1]*A[i+1]...*A[N-1].

所以将A的每一项相乘一次，然后将其放入N的for循环内的所有B是O(N)。

Answer 2

我建议生成更大的输入来测试时间复杂度，例如 N1=100000、N2=200000 ...。对于小输入和小时间帧，编译器、缓存和其他进程可能会影响您测量的时间，不应成为您分析的一部分。

你的算法对我来说看起来是 O(N)，因为 find_solution() 是常数时间并且不会被调用超过一些常数时间。一个非常酷和有创意的问题解决方案，但是，当您回答“什么乘以分母等于分子”的问题时，您可能只是在重新发明除法。

我稍微思考一下的解决办法是对每个索引计算所有元素向右的乘积，这个可以在O(N)时间内完成。对另一边做同样的事情，将边相乘得到 B，对吧？

编辑：此外，在讨论时间复杂度时，测量很好，但它们不能“证明”时间复杂度，必须通过了解算法不同部分的时间复杂度并分析多少次来手动完成东西是运行.

我怎么知道这个函数是否在时间 O(N) 和内存 O(N) 内工作？

How do I know if this function works in time O(N) and memory O(N)?

c++

arrays

big-o