6-5 使用函数求特殊a串数列和 (10 分)
时间: 2023-04-29 22:01:49 浏览: 121
使用函数求特殊a串数列和
题目描述
给定两个正整数a和n,求由a重复n次相加所构成的数列的和。
输入格式
输入在一行中给出正整数a和n(1≤a,n≤100)。
输出格式
在一行中输出该数列的和。
输入样例
2 3
输出样例
14
算法1
(暴力枚举) $O(n)$
直接循环n次,每次将a累加到sum中即可。
时间复杂度
循环n次,时间复杂度为O(n)。
C++ 代码
算法2
(递归) $O(\log n)$
将n分为两半,分别计算a的n/2次方的和,然后将两个和相加即可。
时间复杂度
每次递归将n减半,时间复杂度为O(logn)。
C++ 代码
阅读全文