文章是我在2011年，写在某sdn的。搬运过来。
在编程面试中，大数运算题常常作为一道难题出现，考验着开发者对算法效率的理解与掌握。本文将分享一次从O(n³)到O(n²)时间复杂度优化的实战经验，通过具体案例，带你领略算法优化的魅力。
背景介绍
大数运算，尤其是大数乘法，因其涉及大量位数，传统计算机中的基本数据类型（如int, long等）往往无法满足需求。因此，实现一个能够处理任意长度数字的乘法算法显得尤为重要。
初始尝试：笔算方法的直接映射
最初，我采用了一种直观的方法，将手算乘法的过程直接转换为代码实现。虽然保证了计算的正确性，但其时间复杂度高达O(n³)，显然无法应对大规模数据的运算需求。
算法优化：向O(n²)迈进
经过一番研究与思考，我发现了更高效的算法策略，将时间复杂度成功降至O(n²)。关键在于利用int类型的临时存储，避免了每次累加后的进位检查，而是统一在所有累加完成后进行。这一改进显著提升了运算速度，尤其是在处理长串数字时效果尤为明显。
实现细节
在具体实现上，我采用了动态分配的整型数组r来存储中间结果，随后通过循环处理进位，确保最终结果的准确性。此外，还特别注意了非零索引的查找，以避免不必要的零前缀。
测试与验证
在一系列测试中，该优化后的算法展现出色的性能。以两个2000位数的乘法为例，平均耗时仅为90多毫秒，而200位数的乘法则仅需1毫秒左右，充分验证了O(n²)复杂度的预期表现。
代码示例
以下是优化后的大数乘法函数实现，包括了必要的辅助函数与主程序逻辑：
Cpp
#include <iostream> #include <assert.h> #include <stdio.h> #include <time.h> #include <windows.h> #include <malloc.h> using namespace std; const int MAX = 2001; char num1[MAX]; char num2[MAX]; char result[2*MAX]; void SafeGetNumFromStr ( char* num, char* str); char* BigIntMultiply ( const char * const a, const char * const b , char* const lresult); void multiply( const char *a, const char *b); int main(int argc, char *argv[]) { //test speed cout<<"\n\nspeed test... Number of digits is : "<<MAX-1<<"\n"; int i; const int TEST_TIME = 20; srand((unsigned)time(NULL)); for(i = 0;i<MAX;i++) { num1[i] = 0; num2[i] = 0; } //create data with random for(i = 0; i< MAX - 1; i++) { num1[i] = rand()%10 + '0'; num2[i] = rand()%10 + '0'; } SYSTEMTIME wtm; GetLocalTime(&wtm); long long time_start = wtm.wMilliseconds + wtm.wSecond * 1000; cout<<num1<<endl; cout<<"*\n"; cout<<num2<<endl; for(i = 0; i<TEST_TIME; i++) { BigIntMultiply(num1,num2,result); } GetLocalTime(&wtm); cout<<"Result is:\n"; cout<<result<<endl; double tmv = (double)(wtm.wMilliseconds + wtm.wSecond * 1000 - time_start); cout<<"Test Over. "<<TEST_TIME<<" loops use time: "<<tmv<<" ms\n"; cout<<" Each One Time Use: "<<tmv/(double)TEST_TIME<<" ms\n\n\n"; //test validation cout<<"Validation work...\n"; long long testNum1; long long testNum2; int testI; for(testNum1 = 0;testNum1<1000000000000000;testNum1 = (testNum1+1)*181+1) for(testI= 0;testI<200; testI++) { char a[2*MAX]; char b[2*MAX]; testNum2 = (testNum1+testI)<0?0:testNum1+testI; for(i = 0;i<MAX;i++) { num1[i] = 0; num2[i] = 0; } itoa(testNum1,a,10); itoa(testNum2,b,10); SafeGetNumFromStr(num1,a); SafeGetNumFromStr(num2,b); BigIntMultiply(num1,num2,result); if(8 == testNum2%10) if(testNum1*testNum2 == atoi(result)) cout<<testNum1<<" * "<<testNum2<<" == "<<testNum1*testNum2<<" Correct!\n"; else cout<<testNum1<<" * "<<testNum2<<" Result:"<<result<<"\n"; } //free test cout<<"Now ..... Free Test!\n"; while(1) { char a[2*MAX]; char b[2*MAX]; cout<<"\n\ninput long integer for A"<<endl; cin>>a; cout<<"input long integer for B"<<endl; cin>>b; //get data SafeGetNumFromStr(num1,a); SafeGetNumFromStr(num2,b); cout<<endl<<endl; cout<<num1; cout<<" * "; cout<<num2; cout<<endl; BigIntMultiply(num1,num2,result); cout<<"Result is:"<<endl; cout<<result; } system("pause"); return 0; } void SafeGetNumFromStr( char* num, char* str) { memset(num,0,sizeof(num[0])*MAX); int i; int index = 0; for(i=0;i<2*MAX && index < MAX;i++) { if(str[i] <= '9' && str[i] >='0') num[index++] = str[i]; if('\0'==str[i]) break; } assert( 0 != index ); } char* BigIntMultiply ( const char * const a, const char * const b , char* const lresult) { int i,j; int la = strlen(a); int lb = strlen(b); int rlen = la+lb; int* r = (int*)calloc( rlen, sizeof(int) ); for(i = 0;i < lb; i++) for(j = 0; j < la; j++) r[rlen - 1 - i - j] += (b[lb - i - 1] - '0') * (a[la - j - 1] - '0'); //then is there carry on current number for(j = rlen - 1; j >= 1; j--) if(r[j] > 9) { r[j-1] += r[j] / 10; r[j] %= 10; } //find first none_zero_index for(i = 0; 0 == r[i]; i++){} //mem cpy for(j=0; i< rlen; i++,j++) lresult[j] = r[i]+'0'; lresult[j]='\0'; free(r); return lresult; }
总结与展望
通过本次算法优化之旅，我们不仅实现了从O(n³)到O(n²)的飞跃，更深刻理解了算法设计与数据结构选择的重要性。在后续的探索中，我们还将继续挑战更高效的大数运算算法，如Karatsuba算法，进一步提升计算效率。
注意事项
值得注意的是，尽管优化后的算法在多数情况下表现出色，但在极端条件下，如数字位数接近int的最大表示范围时，仍存在溢出风险。因此，在实际应用中，还需考虑更高级的数据类型或库支持，以确保算法的鲁棒性与通用性。
通过本文的分享，希望能激发你对算法优化的兴趣
