我一直在研究算法效率，一门课程的一部分说，计算操作次数(而不是算法的计时)取决于函数的实现方式(这是作为缺点编写的)，它还取决于算法(这是作为优点编写的)。
这到底是什么意思？两段代码是同一算法的两个不同实现意味着什么(我在这里遗漏了一些微妙之处，还是只是意味着两个做同样事情但语法略有不同的函数算作同一算法的两个独立实现)？它依赖于算法的事实如何好，但它依赖于实现的事实不好？
两者都不正确，真相在中间的某个地方。 该算法什么都不是，也许在30 +年前，但是今天编译器可以解构您的算法并以不同的方式重建它(如果它已被编程为识别您要做什么)。
数学上：你可能在小学听过一个关于将所有数字从 1 到 100 相加，使从 0 到 100 更容易，所以这是 99 或 100 加法运算是吗？ 加上一个循环，它是一个计数器和一个比较。 好吧，如果你意识到 0+100 = 100， 99+1 = 100， 98+2 = 100 会怎样？ 有 50 对加起来是 100，然后自己剩下 50 对。 因此，我们可以减少 100 个加法和一个包含 100 个加法的循环，并将比较降低到 50*100+50 或 50*101。 一次乘法。 您可能可以制作一个具有一些约束的算法，但将 0 到 N 的所有数字相加，N 为正作为约束，即使 N 的奇数值与奇数值会产生不同的通用算法，也许，也许不是，可能有一个 N/2 在那里和一些乘法，也许是一个加法。 比在循环中进行 N 次加法便宜得多，循环变量必须进行多次加法和比较。
但是实现呢：
00000000 <fun1>:
0: e59f0000 ldr r0, [pc] ; 8 <fun1+0x8>
4: e12fff1e bx lr
8: 000013ba ; <UNDEFINED> instruction: 0x000013ba
0000000c <fun2>:
c: e59f0000 ldr r0, [pc] ; 14 <fun2+0x8>
10: e12fff1e bx lr
14: 000013ba ; <UNDEFINED> instruction: 0x000013ba
00000018 <fun3>:
18: e59f0000 ldr r0, [pc] ; 20 <fun3+0x8>
1c: e12fff1e bx lr
20: d783574e strle r5, [r3, lr, asr #14]
算法在这种情况下无关紧要，请注意，编译器甚至将伪随机求和循环简化为答案。
unsigned int fun1 ( unsigned int x )
{
return(x*10);
}
unsigned int fun2 ( unsigned int x )
{
return((x<<3)+(x<<1));
}
unsigned int fun3 ( unsigned int x )
{
return(((x<<2)+x)<<1);
}
我希望乘法，但当然没有得到，也许我需要指定 CPU。
00000000 <fun1>:
0: e0800100 add r0, r0, r0, lsl #2
4: e1a00080 lsl r0, r0, #1
8: e12fff1e bx lr
0000000c <fun2>:
c: e1a03080 lsl r3, r0, #1
10: e0830180 add r0, r3, r0, lsl #3
14: e12fff1e bx lr
00000018 <fun3>:
18: e0800100 add r0, r0, r0, lsl #2
1c: e1a00080 lsl r0, r0, #1
20: e12fff1e bx lr
它不需要识别fun2，其他的都是一样的。 我已经看到 mips 后端实际上在中途调用另一个，因此在这种情况下，fun3 会分支到地址 0，例如，这比仅仅运行指令的成本更高，在这个问题上没有为我做，所以也许我需要一个更复杂的函数。
现在假设 x 是偶数
unsigned int fun1 ( unsigned int x )
{
unsigned int ra;
unsigned int rb;
rb=0;
for(ra=0;ra<=x;ra++) rb+=ra;
return(rb);
}
unsigned int fun2 ( unsigned int x )
{
return((x/2)*(x+1));
}
我们应该得到一个不同的结果，编译器不是那么聪明......
00000000 <fun1>:
0: e3a02000 mov r2, #0
4: e1a03002 mov r3, r2
8: e0822003 add r2, r2, r3
c: e2833001 add r3, r3, #1
10: e1500003 cmp r0, r3
14: 2afffffb bcs 8 <fun1+0x8>
18: e1a00002 mov r0, r2
1c: e12fff1e bx lr
00000020 <fun2>:
20: e1a030a0 lsr r3, r0, #1
24: e2802001 add r2, r0, #1
28: e0000293 mul r0, r3, r2
2c: e12fff1e bx lr
我们假设乘法很便宜，文档会说一个时钟，但这不一定是真的，有一个管道，他们可以通过消耗更多并将时间埋在管道中来节省大量的芯片空间，或者正如您在非管道处理器中看到的那样，乘法的时钟更长。 我们可以假设它埋在管道中，如果你能保持管道平稳移动，它真的很快。
无论如何，我们可以安全地假设最后一个示例的加法循环比优化算法慢得多。 因此，算法和实现在这里帮助我们。
unsigned int fun1 ( unsigned int x )
{
return(x/10);
}
00000000 <fun1>:
0: e59f3008 ldr r3, [pc, #8] ; 10 <fun1+0x10>
4: e0821390 umull r1, r2, r0, r3
8: e1a001a2 lsr r0, r2, #3
c: e12fff1e bx lr
10: cccccccd stclgt 12, cr12, [r12], {205} ; 0xcd
这是一个有趣的，我可以/已经证明，如果您的处理器有除法，乘以 1/5 或 1/10 的解决方案比直除法慢，有额外的负载，有移位和乘法，其中除法可能是负载和除法。 您必须使内存变慢，以便额外的负载和额外的获取吞噬差异，这里的除法通常乘以较慢。 但是编译器在大多数情况下仍然是正确的，乘法更快，所以这个解决方案是可以的。 但是它没有直接实现我们要求的操作，因此算法从所需的算法更改为其他算法。 实现保存了算法，或者至少没有伤害它。
查找FFT，这是一个经典的例子，从具有一定数学量的基本算法开始，您可以计算操作，然后通过各种方式重新排列数据/操作以减少该数学，并进一步减少它。 这很好，在这种情况下，您很可能会帮助编译器。 但是，如果你允许它，实现可能会进一步帮助，特别是你如何编写代码可以采用一个伟大的算法并使其变得更糟。
unsigned int fun1 ( unsigned int x )
{
return(x*10.0);
}
00000000 <fun1>:
0: ee070a90 vmov s15, r0
4: ed9f6b05 vldr d6, [pc, #20] ; 20 <fun1+0x20>
8: eeb87b67 vcvt.f64.u32 d7, s15
c: ee277b06 vmul.f64 d7, d7, d6
10: eefc7bc7 vcvt.u32.f64 s15, d7
14: ee170a90 vmov r0, s15
18: e12fff1e bx lr
1c: e1a00000 nop ; (mov r0, r0)
20: 00000000 andeq r0, r0, r0
24: 40240000 eormi r0, r4, r0
unsigned int fun1 ( unsigned int x )
{
return(x*10.0F);
}
00000000 <fun1>:
0: ee070a90 vmov s15, r0
4: ed9f7a04 vldr s14, [pc, #16] ; 1c <fun1+0x1c>
8: eef87a67 vcvt.f32.u32 s15, s15
c: ee677a87 vmul.f32 s15, s15, s14
10: eefc7ae7 vcvt.u32.f32 s15, s15
14: ee170a90 vmov r0, s15
18: e12fff1e bx lr
1c: 41200000 ; <UNDEFINED> instruction: 0x41200000
微妙，需要一个 32 位常量与 64 位常量，数学是单对双，采用更复杂的算法来加起来。 最后，我们能做一个固定点乘法并得到相同的结果吗？
unsigned int fun1 ( unsigned int x )
{
return((((x<<1)*20)+1)>>1);
}
00000000 <fun1>:
0: e0800100 add r0, r0, r0, lsl #2
4: e1a00180 lsl r0, r0, #3
8: e1a000a0 lsr r0, r0, #1
c: e12fff1e bx lr
无论如何，x 是整数会有任何四舍五入吗？
无论哪种方式都没有事实，实现无关紧要也不是事实(即使在有一块小黑板与几块黑板的教室里，或者白板的标记持续时间更长并且同样容易擦除)这不是算法无关紧要的事实，编程语言无关紧要不是事实， 编译器无关紧要不是事实，编译器选项无关紧要这不是事实，处理器无关紧要也不是事实。
定时您的算法执行并不是全部，总而言之，我可以很容易地证明相同的机器代码在同一处理器和系统上运行得更慢或更快，而无需执行更改时钟速度等操作。 对算法进行计时以将误差添加到结果中的方法并不少见。 想要快速完成一个系统，时间，调整，时间，调整。 有时调整涉及尝试不同的算法。 对于一系列类似的系统，相同的交易，但了解性能收益的来源，并根据这些因素在目标系列中的变化进行调整。
算法很重要是一个事实。实现很重要是一个事实。
请注意，没有理由与您的教授发生争执，我会称之为事实，通过课程，通过它，然后继续前进。 选择你的战斗，就像你在现实世界中与你的老板或同事一样。 但是，与现实世界不同，你完成了这个学期，也许永远完成了那门课，现实世界你可能会有那些同事和老板很长一段时间，一场糟糕的战斗或一场失败的战斗会影响你很长时间。 即使你是对的。
不能说出课程作者的意思，但也许我可以清除你的第二个问题。
算法是对实现某个目标/计算所需操作的描述。它最常用数学语言给出。计算机程序是实现算法的一种方式[1]，也是最常见的。即使它们是相当抽象的东西，它们仍然比数学描述更具体。它们与编写它们的编程语言和环境有关，它有各种怪癖，你试图解决的问题的细节[2]，甚至是编写它的特定工程师。因此，实现某种算法的两个程序或程序的一部分是不同的，甚至具有不同的性能属性是很自然的。因此，为某个输入执行的指令数肯定会落入属性桶中，这些属性在两个实现之间有所不同。
[1]另一种方式可能是在硬件中，如数字电路或模拟计算机，或通过一些机械过程，如时钟或19世纪的机械自动机之一，甚至是一些生物或化学过程。 [2] 为了澄清，通用排序例程的编写方式可能与 16 位整数排序例程不同，即使它们都实现了 QuickSort。