4-11 DSA

从今天起 会不定期分享一些
自己在学习DSA漫漫长路中遇到的一些有趣的问题
文章包含
问题集「问题的归类」 问题「按序排列」 拓展「按需出现」
解决「问题解法」 图解「博主手绘的思路哈哈」

问题集

  • 交换变量
  • 时间复杂度求解

问题1

不依靠中间变量(附加空间)交换两个变量内容

解决

  • 加减法
1
2
3
a += b;
b = a - b;
a -= b;
  • 异或法
1
2
3
a = a ^ b;
b = a ^ b;
a = a ^ b;

大家可以验证下哦~

问题2

关于计算时间复杂度
将n以内整数依次相加,但最多加到和为n,即1+2+…<=n
博主实现代码

1
2
3
4
5
6
7
8
9
10
11
int sum = 0;
int n = 10;
for(int i = 1; i <= n; i++)
{
if (sum + i <= n) {
sum += i;
} else {
std::cout << "循环了" << i - 1 << "次" << std::endl;
break;
}
}

发现算出来的时间复杂度和答案不同🤦‍♂️

解决

假设循环体循环次数为k
得 sum = 1 + 2 + 3 + ….. + k = k(k + 1) / 2
又 sum <= n
得 k(k + 1) / 2 <= n
即T(n) = O(n^1/2)

问题3

编写代码 将二维数组中第1,2,4,8…行的对角元之前的元素清空 求时间复杂度
采用C++编写

解决

1
2
3
4
5
6
7
8
9
int n = 3;
int A [n][n];
for(int i = 1; i <= n; i*=2)
{
for(int j = 0; j < i; j++)
{
A[i][j] = 0;
}
}

由题可得 i*=2 即进行2的幂运算
外循环次数即 log(2)n 内循环次数即 i
执行次数为
log(2)n
∑ 2k = 1+2+2^2+2^3…+2^log(2)n = 2^log(2)n+1 = 2n-1
k=0

即T(n) = O(n)

# DSA

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×