c++ - 如何证明以下算法的正确性？

Question

我需要证明以下算法正确工作，我知道归纳法，但不知道如何在这里使用它？如果知道算法的复杂性，我会很高兴，它有多优化？它的运行时间是多少？请帮助我

#include <cstdlib>
#include <iostream>
#define c 2
//we should take c   more ot equal  then 2
using namespace std;
int multiply(int y,int z){
      // product yz
    if(z==0) return 0;
    return (multiply(c*y,int(z/c))+y*(z %c));
}

int main(int argc, char *argv[])
{
    int y=5;
    int z=7;
    cout<<multiply(y,z)<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

谢谢

Answer 1

1) z=0你的功能显然是正确的

2) 假设multiply(x, y)返回 x*y对于 0 <= y < y0 .然后

  x*y
= x*((y/c)*c + y%c)    # by the definition of %
= x*c*(y/c) + x*(y%c)  # distributive, commutative laws
= multiply(x*c, y/c) + x*(y%c) # 0 <= y/c < y, induction hypothesis