多少条指令作为输入大小为N的函数

本文关键字：小为 函数 输入 指令 多少 | 更新日期: 2023-09-27 18:10:00

我有以下代码

        int cnt = 0;
        for (int i = 0; i < N; ++i)
        {
            for (int j = i + 1; j < N; ++j)
            {
               ...
            }
        }

声明变量的次数是多少?

第一次- int cnt = 0;

第二次- int i = 0;

n次- int j = i+1;

所以答案是N+2。我对这个

使用了普林斯顿分析http://www.cs.princeton.edu/courses/archive/spring15/cos226/lectures/14AnalysisOfAlgorithms.pdf

33幻灯片

这是对的吗?或者编译器只是重新赋值了一个j?所以我们只申报了3次?

你能提供一个关于这个问题的深入解释(包括汇编代码)吗?那么对象类型(不是int)呢?

多少条指令作为输入大小为N的函数

您可以说您声明 j一次，或者您声明 j N次，因为声明仅是分析源的问题。所以:

我声明了一次j;在一个循环内。

我在每次处理循环时声明j。

同样有用。

它们都说明了一些关于源代码的内容，并且都没有说明计算机在实际运行代码时所做的工作。

声明是源代码问题，而不是运行代码问题。算法是运行代码的问题。

现在，当涉及到生成的代码时，可能会有是用于j的单个内存块，尽管该"内存";很可能是寄存器而不是实际的RAM。

该算法是O(n²)，因为它运行n * n / 2 - n / 2次，并且忽略低阶(即O(0.5n²))和忽略常数乘子(即O(n²))。

现在考虑:

int loops = (N + 3) / 4;
int i = 0;
switch(N % 4)
{
    case 0: 
    for (int j = ++i; j < N; ++j)
    {
        …
    }
    goto case 3;
    case 3:
    for (int j = ++i; j < N; ++j)
    {
        …
    }
    goto case 2;
    case 2:
    for (int j = ++i; j < N; ++j)
    {
        …
    }
    goto case 1;
    case 1:
    for (int j = ++i; j < N; ++j)
    {
        …
    }
    if (--loops > 0) goto case 0;
    break;
}

这里我们有一个非常不同的结构，循环次数少了4次，但结果相同。

它也是O(n)因为它也运行了n * n / 2 - n / 2次。事实上，int j出现了4次，这并不意味着什么。考虑进一步:

int loops = (N + 3) / 4;
int i = 0;
switch(N % 4)
{
    case 0: 
    for (int j = ++i; j < N; ++j)
    {
        …
    }
    goto case 3;
    case 3:
    for (int k = ++i; k < N; ++k)
    {
        …
    }
    goto case 2;
    case 2:
    for (int m = ++i; m < N; ++m)
    {
        …
    }
    goto case 1;
    case 1:
    for (int p = ++i; p < N; ++p)
    {
        …
    }
    if (--loops > 0) goto case 0;
    break;
}

在算法上并没有什么不同，尽管它声明了"不管你怎么看，都比以前少了四倍。

声明不是指令。他们说"我们要用这种方式来谈论这件事"，说明说"这样做"。

这是对的吗?或者编译器只是重新赋值了一个j?所以我们只申报了3次?

这不是正确的问题。就。net而言，这个过程比C/c++更复杂。虚拟机在IL代码上运行。它的IL代码应该是基于堆栈的。IL代码将被优化为在执行方法体之前声明要在堆栈中使用的局部变量。它通过.locals指令做到这一点。因此，虚拟机只能使用一个变量，即堆栈，并以任何方式管理内存。

    int cnt = 0;
    int N = 100;
    for (int i = 0; i < N; ++i)
    {
        for (int j = i + 1; j < N; ++j)
        {
            cnt++;
        }
    }
    Console.WriteLine("cnt=" + cnt);

IL代码:

    .locals init ([0] int32 cnt,
             [1] int32 N,
             [2] int32 i,
             [3] int32 j)
    IL_0000:  ldc.i4.0
    IL_0001:  stloc.0
    IL_0002:  ldc.i4.s   100
    IL_0004:  stloc.1
    IL_0005:  ldc.i4.0
    IL_0006:  stloc.2
    IL_0007:  br.s       IL_001f
    IL_0009:  ldloc.2
    IL_000a:  ldc.i4.1
    IL_000b:  add                   // here we have on stack i + 1
    IL_000c:  stloc.3               // variable j set to what's on stack
    IL_000d:  br.s       IL_0017
    IL_000f:  ldloc.0
    IL_0010:  ldc.i4.1
    IL_0011:  add
    IL_0012:  stloc.0
    IL_0013:  ldloc.3
    IL_0014:  ldc.i4.1
    IL_0015:  add
    IL_0016:  stloc.3               // variable j set
    IL_0017:  ldloc.3
    IL_0018:  ldloc.1
    IL_0019:  blt.s      IL_000f    // j < N compare (1th and 3th positions)
    IL_001b:  ldloc.2
    IL_001c:  ldc.i4.1
    IL_001d:  add
    IL_001e:  stloc.2
    IL_001f:  ldloc.2
    IL_0020:  ldloc.1
    IL_0021:  blt.s      IL_0009
    IL_0023:  ldstr      "cnt="
    IL_0028:  ldloc.0
    IL_0029:  box        [mscorlib]System.Int32
    IL_002e:  call       string [mscorlib]System.String::Concat(object,
                                                                object)
    IL_0033:  call       void [mscorlib]System.Console::WriteLine(string)
    IL_0038:  ret

所以最好是基于堆栈而不是单个变量来讨论内存分配。

p。

相关文章：