跳到内容
当前位置:首页>高中教材>小学课本里的“高斯求和公式(从1加到10亿)”,竟帮 C 语言省掉 10 亿次循环

小学课本里的“高斯求和公式(从1加到10亿)”,竟帮 C 语言省掉 10 亿次循环

  • 2026-11-22 19:18:30
小学课本里的“高斯求和公式(从1加到10亿)”,竟帮 C 语言省掉 10 亿次循环

还记得小学数学课本里那个经典的“高斯算术”故事吗?

8 岁的小高斯面对老师布置的 1 + 2 + 3 + ... + 100,没有像其他同学一样埋头苦算,而是发现首尾相加都等于 101,直接用 (1 + 100) × 100 ÷ 2 = 5050 秒杀了全班。

长大后,很多人会觉得:“现在都有计算机了,算得那么快,直接让电脑硬算不就行了,学这些公式还有什么用?”

今天,我们就用号称“运行速度最快”的 C 语言,让“电脑蛮力死算”和“小学高斯公式”来一场正面 PK,看看差距到底有多大。

高斯求和公式与循环的对比

第一回合:C 语言的“蛮力死算”

假设我们现在要计算从 1 加到 10 亿(1,000,000,000)的总和。

对于电脑来说,最符合直觉的做法就是写一个 for 循环,从 1 开始一个一个往上加。我们请出 C 语言的计时工具 <time.h>,看看它需要跑多久:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>#include <time.h>int main() {    long long n = 1000000000; // 10亿    long long sum = 0;    clock_t start = clock(); // 开始计时    // 蛮力死算:老老实实加10亿次    for (long long i = 1; i <= n; i++) {        sum += i;    }    clock_t end = clock(); // 结束计时    double time_used = (double)(end - start) / CLOCKS_PER_SEC;    printf("死算结果:%lld\n", sum);    printf("消耗时间:%f 秒\n", time_used);    return 0;}

运行结果(本文示例在关闭编译器优化 -O0 下测得):

死算结果:500000000500000000消耗时间:0.87 秒

为了算一个加法,CPU 狂转了将近 1 秒。如果把数字改成 100 亿,耗时就要再乘上 10 倍。

这里有个细节值得先说清楚:同样的代码,开不开编译优化,结果天差地别。 我把上面这段用 -O2 重新编译再跑,耗时直接变成 0.000003 秒——因为编译器足够聪明,它认出了这是一个等差数列求和,悄悄把循环替换成了公式。所以“蛮力死算”只有在关掉优化、并且编译器不做这类优化时才会真正发生。这是理解后面结论的前提。

另一个必须提醒的坑是类型溢出:这里必须用 long long。如果用普通的 int,10 亿求和的结果高达 5×10¹⁷,早就超出了 int 能表示的上限(约 21 亿),算出来的会是一个负数(实测是 -243309312)。

第二回合:请出“高斯求和公式”

现在,我们把中间那几行循环删掉,直接换上小学课本里背过的高斯求和公式:总和 = (首项 + 末项) × 项数 ÷ 2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>#include <time.h>int main() {    long long n = 1000000000; // 10亿    long long sum = 0;    clock_t start = clock(); // 开始计时    // 高斯公式:不管n有多大,只算1次    sum = (1 + n) * n / 2;    clock_t end = clock(); // 结束计时    double time_used = (double)(end - start) / CLOCKS_PER_SEC;    printf("公式结果:%lld\n", sum);    printf("消耗时间:%f 秒\n", time_used);    return 0;}

运行结果:

公式结果:500000000500000000消耗时间:0.000003 秒

速度快到几乎超出计时器的精度,直接逼近 0 秒。

不过公式版也不是绝对安全:(1 + n) * n 这个中间乘积会先算出来,当 n 达到 100 亿时,这个中间值会超过 long long 的上限而溢出,得到错误结果。所以用公式时,同样要留意 n 的取值边界。

总结:为什么程序员必须懂数学

在这场对决里:

• 蛮力循环: 数据扩大 10 倍,时间就变慢 10 倍,这叫 O(n) 复杂度(前提是编译器没有帮你优化掉循环)。

• 高斯公式: 不管你是算 100、10 亿还是 1000 亿,永远只需要 1 次加法、1 次乘法、1 次除法,这叫 O(1) 复杂度。

哪怕你的电脑显卡再贵、CPU 再强,在小学数学公式面前,蛮力也只能甘拜下风。 这就是算法与数学的魅力。

课后思考:平方和怎么办?

如果把题目稍微改难一点,变成求平方和:1² + 2² + 3² + ... + n²,难道电脑就只能老老实实循环了吗?

其实初中数学里也藏着一个对应的高斯式公式:

1² + 2² + ... + n² = n(n + 1)(2n + 1) / 6

把它写进 C 语言,同样只用几次乘法除法就能算完:

1
long long sum_sq = n * (n + 1) * (2 * n + 1) / 6;

实测 n = 10 亿时,结果是 1264157736636763221。你看,换汤不换药,数学公式依旧能“秒杀”循环。


欢迎转载,转载时请:保留本文标题、作者和公众号名称

基本 文件 流程 错误 SQL 调试
  1. 请求信息 : 2026-11-23 07:16:09 HTTP/1.1 GET : http://c.sjds.net/a/495582.html
  2. 运行时间 : 0.109384s [ 吞吐率:9.14req/s ] 内存消耗:4,323.91kb 文件加载:140
  3. 缓存信息 : 0 reads,0 writes
  4. 会话信息 : SESSION_ID=60f472794505c5774508609de3ef9f41
  1. /www/wwwroot/c.sjds.net/public/index.php ( 0.79 KB )
  2. /www/wwwroot/c.sjds.net/vendor/autoload.php ( 0.17 KB )
  3. /www/wwwroot/c.sjds.net/vendor/composer/autoload_real.php ( 2.49 KB )
  4. /www/wwwroot/c.sjds.net/vendor/composer/platform_check.php ( 0.90 KB )
  5. /www/wwwroot/c.sjds.net/vendor/composer/ClassLoader.php ( 14.03 KB )
  6. /www/wwwroot/c.sjds.net/vendor/composer/autoload_static.php ( 4.90 KB )
  7. /www/wwwroot/c.sjds.net/vendor/topthink/think-helper/src/helper.php ( 8.34 KB )
  8. /www/wwwroot/c.sjds.net/vendor/topthink/think-validate/src/helper.php ( 2.19 KB )
  9. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/helper.php ( 1.47 KB )
  10. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/stubs/load_stubs.php ( 0.16 KB )
  11. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Exception.php ( 1.69 KB )
  12. /www/wwwroot/c.sjds.net/vendor/topthink/think-container/src/Facade.php ( 2.71 KB )
  13. /www/wwwroot/c.sjds.net/vendor/symfony/deprecation-contracts/function.php ( 0.99 KB )
  14. /www/wwwroot/c.sjds.net/vendor/symfony/polyfill-mbstring/bootstrap.php ( 8.26 KB )
  15. /www/wwwroot/c.sjds.net/vendor/symfony/polyfill-mbstring/bootstrap80.php ( 9.78 KB )
  16. /www/wwwroot/c.sjds.net/vendor/symfony/var-dumper/Resources/functions/dump.php ( 1.49 KB )
  17. /www/wwwroot/c.sjds.net/vendor/topthink/think-dumper/src/helper.php ( 0.18 KB )
  18. /www/wwwroot/c.sjds.net/vendor/symfony/var-dumper/VarDumper.php ( 4.30 KB )
  19. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/App.php ( 15.30 KB )
  20. /www/wwwroot/c.sjds.net/vendor/topthink/think-container/src/Container.php ( 15.76 KB )
  21. /www/wwwroot/c.sjds.net/vendor/psr/container/src/ContainerInterface.php ( 1.02 KB )
  22. /www/wwwroot/c.sjds.net/app/provider.php ( 0.19 KB )
  23. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Http.php ( 6.04 KB )
  24. /www/wwwroot/c.sjds.net/vendor/topthink/think-helper/src/helper/Str.php ( 7.29 KB )
  25. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Env.php ( 4.68 KB )
  26. /www/wwwroot/c.sjds.net/app/common.php ( 0.03 KB )
  27. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/helper.php ( 18.78 KB )
  28. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Config.php ( 5.54 KB )
  29. /www/wwwroot/c.sjds.net/config/app.php ( 0.95 KB )
  30. /www/wwwroot/c.sjds.net/config/cache.php ( 0.78 KB )
  31. /www/wwwroot/c.sjds.net/config/console.php ( 0.23 KB )
  32. /www/wwwroot/c.sjds.net/config/cookie.php ( 0.56 KB )
  33. /www/wwwroot/c.sjds.net/config/database.php ( 2.48 KB )
  34. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/facade/Env.php ( 1.67 KB )
  35. /www/wwwroot/c.sjds.net/config/filesystem.php ( 0.61 KB )
  36. /www/wwwroot/c.sjds.net/config/lang.php ( 0.91 KB )
  37. /www/wwwroot/c.sjds.net/config/log.php ( 1.35 KB )
  38. /www/wwwroot/c.sjds.net/config/middleware.php ( 0.19 KB )
  39. /www/wwwroot/c.sjds.net/config/route.php ( 1.89 KB )
  40. /www/wwwroot/c.sjds.net/config/session.php ( 0.57 KB )
  41. /www/wwwroot/c.sjds.net/config/trace.php ( 0.34 KB )
  42. /www/wwwroot/c.sjds.net/config/view.php ( 0.82 KB )
  43. /www/wwwroot/c.sjds.net/app/event.php ( 0.25 KB )
  44. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Event.php ( 7.67 KB )
  45. /www/wwwroot/c.sjds.net/app/service.php ( 0.13 KB )
  46. /www/wwwroot/c.sjds.net/app/AppService.php ( 0.26 KB )
  47. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Service.php ( 1.64 KB )
  48. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Lang.php ( 7.35 KB )
  49. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/lang/zh-cn.php ( 13.70 KB )
  50. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/initializer/Error.php ( 3.31 KB )
  51. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/initializer/RegisterService.php ( 1.33 KB )
  52. /www/wwwroot/c.sjds.net/vendor/services.php ( 0.14 KB )
  53. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/service/PaginatorService.php ( 1.52 KB )
  54. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/service/ValidateService.php ( 0.99 KB )
  55. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/service/ModelService.php ( 2.04 KB )
  56. /www/wwwroot/c.sjds.net/vendor/topthink/think-trace/src/Service.php ( 0.77 KB )
  57. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Middleware.php ( 6.72 KB )
  58. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/initializer/BootService.php ( 0.77 KB )
  59. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/Paginator.php ( 11.86 KB )
  60. /www/wwwroot/c.sjds.net/vendor/topthink/think-validate/src/Validate.php ( 63.20 KB )
  61. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/Model.php ( 23.55 KB )
  62. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/model/concern/Attribute.php ( 21.05 KB )
  63. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/model/concern/AutoWriteData.php ( 4.21 KB )
  64. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/model/concern/Conversion.php ( 6.44 KB )
  65. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/model/concern/DbConnect.php ( 5.16 KB )
  66. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/model/concern/ModelEvent.php ( 2.33 KB )
  67. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/model/concern/RelationShip.php ( 28.29 KB )
  68. /www/wwwroot/c.sjds.net/vendor/topthink/think-helper/src/contract/Arrayable.php ( 0.09 KB )
  69. /www/wwwroot/c.sjds.net/vendor/topthink/think-helper/src/contract/Jsonable.php ( 0.13 KB )
  70. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/model/contract/Modelable.php ( 0.09 KB )
  71. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Db.php ( 2.88 KB )
  72. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/DbManager.php ( 8.52 KB )
  73. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Log.php ( 6.28 KB )
  74. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Manager.php ( 3.92 KB )
  75. /www/wwwroot/c.sjds.net/vendor/psr/log/src/LoggerTrait.php ( 2.69 KB )
  76. /www/wwwroot/c.sjds.net/vendor/psr/log/src/LoggerInterface.php ( 2.71 KB )
  77. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Cache.php ( 4.92 KB )
  78. /www/wwwroot/c.sjds.net/vendor/psr/simple-cache/src/CacheInterface.php ( 4.71 KB )
  79. /www/wwwroot/c.sjds.net/vendor/topthink/think-helper/src/helper/Arr.php ( 16.63 KB )
  80. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/cache/driver/File.php ( 7.84 KB )
  81. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/cache/Driver.php ( 9.03 KB )
  82. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/contract/CacheHandlerInterface.php ( 1.99 KB )
  83. /www/wwwroot/c.sjds.net/app/Request.php ( 0.09 KB )
  84. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Request.php ( 55.78 KB )
  85. /www/wwwroot/c.sjds.net/app/middleware.php ( 0.25 KB )
  86. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Pipeline.php ( 2.61 KB )
  87. /www/wwwroot/c.sjds.net/vendor/topthink/think-trace/src/TraceDebug.php ( 3.40 KB )
  88. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/middleware/SessionInit.php ( 1.94 KB )
  89. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Session.php ( 1.80 KB )
  90. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/session/driver/File.php ( 6.27 KB )
  91. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/contract/SessionHandlerInterface.php ( 0.87 KB )
  92. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/session/Store.php ( 7.12 KB )
  93. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Route.php ( 23.73 KB )
  94. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/route/RuleName.php ( 5.75 KB )
  95. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/route/Domain.php ( 2.53 KB )
  96. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/route/RuleGroup.php ( 22.43 KB )
  97. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/route/Rule.php ( 26.95 KB )
  98. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/route/RuleItem.php ( 9.78 KB )
  99. /www/wwwroot/c.sjds.net/route/app.php ( 1.72 KB )
  100. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/facade/Route.php ( 4.70 KB )
  101. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/route/dispatch/Controller.php ( 4.74 KB )
  102. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/route/Dispatch.php ( 10.44 KB )
  103. /www/wwwroot/c.sjds.net/app/controller/Index.php ( 4.81 KB )
  104. /www/wwwroot/c.sjds.net/app/BaseController.php ( 2.05 KB )
  105. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/facade/Db.php ( 0.93 KB )
  106. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/connector/Mysql.php ( 5.44 KB )
  107. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/PDOConnection.php ( 52.47 KB )
  108. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/Connection.php ( 8.39 KB )
  109. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/ConnectionInterface.php ( 4.57 KB )
  110. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/builder/Mysql.php ( 16.58 KB )
  111. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/Builder.php ( 24.06 KB )
  112. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/BaseBuilder.php ( 27.50 KB )
  113. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/Query.php ( 15.71 KB )
  114. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/BaseQuery.php ( 45.13 KB )
  115. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/concern/TimeFieldQuery.php ( 7.43 KB )
  116. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/concern/AggregateQuery.php ( 3.26 KB )
  117. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/concern/ModelRelationQuery.php ( 20.07 KB )
  118. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/concern/ParamsBind.php ( 3.66 KB )
  119. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/concern/ResultOperation.php ( 7.01 KB )
  120. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/concern/WhereQuery.php ( 19.37 KB )
  121. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/concern/JoinAndViewQuery.php ( 7.11 KB )
  122. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/concern/TableFieldInfo.php ( 2.63 KB )
  123. /www/wwwroot/c.sjds.net/vendor/topthink/think-orm/src/db/concern/Transaction.php ( 2.77 KB )
  124. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/log/driver/File.php ( 5.96 KB )
  125. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/contract/LogHandlerInterface.php ( 0.86 KB )
  126. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/log/Channel.php ( 3.89 KB )
  127. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/event/LogRecord.php ( 1.02 KB )
  128. /www/wwwroot/c.sjds.net/vendor/topthink/think-helper/src/Collection.php ( 16.47 KB )
  129. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/facade/View.php ( 1.70 KB )
  130. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/View.php ( 4.39 KB )
  131. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Response.php ( 8.81 KB )
  132. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/response/View.php ( 3.29 KB )
  133. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/Cookie.php ( 6.06 KB )
  134. /www/wwwroot/c.sjds.net/vendor/topthink/think-view/src/Think.php ( 8.38 KB )
  135. /www/wwwroot/c.sjds.net/vendor/topthink/framework/src/think/contract/TemplateHandlerInterface.php ( 1.60 KB )
  136. /www/wwwroot/c.sjds.net/vendor/topthink/think-template/src/Template.php ( 46.61 KB )
  137. /www/wwwroot/c.sjds.net/vendor/topthink/think-template/src/template/driver/File.php ( 2.41 KB )
  138. /www/wwwroot/c.sjds.net/vendor/topthink/think-template/src/template/contract/DriverInterface.php ( 0.86 KB )
  139. /www/wwwroot/c.sjds.net/runtime/temp/52e0794259aeabc01163982c3f0015ae.php ( 8.05 KB )
  140. /www/wwwroot/c.sjds.net/vendor/topthink/think-trace/src/Html.php ( 4.42 KB )
  1. CONNECT:[ UseTime:0.000664s ] mysql:host=172.18.0.4;port=3306;dbname=c_sjds;charset=utf8mb4
  2. SHOW FULL COLUMNS FROM `fenlei` [ RunTime:0.000952s ]
  3. SELECT * FROM `fenlei` WHERE `fid` = 0 [ RunTime:0.000346s ]
  4. SELECT * FROM `fenlei` WHERE `fid` = 63 [ RunTime:0.000403s ]
  5. SHOW FULL COLUMNS FROM `set` [ RunTime:0.000727s ]
  6. SELECT * FROM `set` [ RunTime:0.000380s ]
  7. SHOW FULL COLUMNS FROM `article` [ RunTime:0.000783s ]
  8. SELECT * FROM `article` WHERE `id` = 495582 LIMIT 1 [ RunTime:0.000404s ]
  9. UPDATE `article` SET `lasttime` = 1795389369 WHERE `id` = 495582 [ RunTime:0.001334s ]
  10. SELECT * FROM `fenlei` WHERE `id` = 66 LIMIT 1 [ RunTime:0.000295s ]
  11. SELECT * FROM `article` WHERE `id` < 495582 ORDER BY `id` DESC LIMIT 1 [ RunTime:0.000397s ]
  12. SELECT * FROM `article` WHERE `id` > 495582 ORDER BY `id` ASC LIMIT 1 [ RunTime:0.000376s ]
  13. SELECT * FROM `article` WHERE `id` < 495582 ORDER BY `id` DESC LIMIT 10 [ RunTime:0.000564s ]
  14. SELECT * FROM `article` WHERE `id` < 495582 ORDER BY `id` DESC LIMIT 10,10 [ RunTime:0.000554s ]
  15. SELECT * FROM `article` WHERE `id` < 495582 ORDER BY `id` DESC LIMIT 20,10 [ RunTime:0.000505s ]
0.121593s