从频度引发的c语言多重for循环乃至编写算法思路的思考

简介: 首先需要声明的是,笔者是一名有C语言基础并正在为考研而复习数据结构的大学生,本篇文章中的for循环代码来自于清华大学严蔚敏教授出版的《数据结构》。本篇博客适用于初学者理解C语言for循环,多重for循环、数据结构频度、线性代数矩阵等知识点。整篇文章从频度开始,讲述两个矩阵相乘算法,最后讲述整个算法的设计原理

频度

for (i=1;i<=n;i++)    //频度为n+1
   for(j=1;j<n;j++)   //频度为n*(n+1)
   {
    c[i][j]=0;        //频度为n^2
    for(k=1;k<=n;k++) //频度为n^2*(n+1)
    c[i][j]=c[i][j]+a[i][k]*b[k][j]; //频度为n^3
    }

这是一段用于两个矩阵相乘的c代码

首先对频度(频度已在代码注释中)进行一下解释:

①for (i=1;i<=n;i++) //频度为n+1

第一个for循环频度是n+1,因为在执行完第n次循环后,执行i++,开始了下一次即n+1次循环,因为n+1次循环碰壁了,什么意思?遇到了i<=n的这堵墙,条件不符合,所以循环结束。


所以实际有效执行次数是n次,但总共执行了n+1次。


②for(j=1;j

第二个for循环的频度是n*(n+1),这里有两个原因:

1.因为第一个for循环实际执行了n次,所以传递给第二个for循环n次。

2.类比第一个for循环,第二个for循环实际执行次数是n次,但最后一次碰壁了,所以总共执行了n+1次

3.总共就是n*(n+1)次


…别问我为什么不是n+(n+1)次,如果有这样疑问的同学需要重新学习一下c语言

③c[i][j]=0; //频度为n^2

本段代码很容易理解了,从第一个for循环和第二个for循环得到的n*n次,因为第一个for循环有效传递了n次,第二个for循环也有效传递了n次


④for(k=1;k<=n;k++) //频度为(n+1)n^2

第三个for循环分为两部分

1.从前两个for循环上得到了n*n次的循环,所以是n^2

2.类似第一个循环,总共执行了(n+1)次

所以一共循环了(n+1)n^2


⑤c[i][j]=c[i][j]+a[i][k]*b[k][j]; //频度为n^3

从三个for循环上得到了n* n *n次循环,所以是n^3次

矩阵相乘过程

下面说明两个矩阵相乘的过程

两个矩阵相乘在线性代数是一个很基础的算法(或者叫算术)

在上述代码中是

c[i][j]=c[i][j]+a[i][k]*b[k][j]; 

其数学概念用一个例子可表示:

20210627224528680.jpg

也就是说新矩阵中的11(第一行第一列,在后面的12或者21就是第一行第二列和第二行第一列)是由

第一个矩阵的第一行X第二个矩阵的第一列

看结果矩阵的字母即看得出,这里不多加叙述


假设第一个矩阵为A矩阵,第二个矩阵为B矩阵,第三个矩阵为C矩阵


下面结合代码和上面的图进行具体的算法分析

计算C矩阵的过程如下

①第一个for循环传递i=1,i<=2,为什么小于2?后面有解释

②第二个for循环传递j=1,j<=2

③c[1][1]=0

④第三个for循环传递k=1,K<=2

⑤c[1][1]=c[1][1]+a[1][1]*b[1][1]

⑥第三个for循环传递k=2

⑦c[1][1]=c[1][1]+a[1][2]*b[2][1] //这里的右值c[1][1]是第5个步骤里的结果

20210627230521412.jpg

至此,C矩阵中C11已计算出来,现在进入到计算C12

①第一个for循环还是1

②第二个for循环传递j=2

③c[1][2]=0

④第三个for循环传递k=1

⑤c[1][2]=c[1][2]+a[1][1]*b[1][2] //注意,b的第二个元素从1变成了2

⑥第三个for循环传递k=2

⑦c[1][2]=c[1][2]+a[1][2]*b[2][2] //这里的右值c[1][2]是第5个步骤里的结果20210627231752240.jpg

当C矩阵中第一行的两个元素计算完后,开始计算C矩阵中的第二行元素,即C21和C22


至此,第一个for循环开始进入i=2时代


我相信现在读者应该对 i 和 j 为什么小于等于2有一定的想法


因为C矩阵的行为2,列为2

c[i][j]最大就是c[2][2]


所以当C矩阵的第一行的两个元素都得出结果后,c[1][?]就变成了c[2][?]


对for循环,大家也应该有个理解了,可以直接看下一段话

第一个for循环传递i=1给第二个for循环

第二个for循环传递j=1给第三个for循环

第三个for循环传递了k=1之后,代码执行到k=2,并执行完后,再返回到第二个for循环

然后

第二个for循环传递j=2给第三个for循环

第三个for循环传递了k=1之后,代码执行到k=2,并执行完后,再返回到第二个for循环

然后 j 到顶了,再返回到第一个for循环,i 就变成了2,再进行一次上面的循环


通俗的来说,里面的for循环循环结束后,才会回到表面的for循环


思考算法的设计原理

下面,我们来思考一下整个算法是怎么由内而外进行设计的


第一个问题,我们看到这段代码,映入眼帘的就是三个for循环(以后你可能会遇到有四五个甚至更多的for循环)那么,这三个for循环是干嘛的?


由第三段代码

c[i][j]=0;

可知,第三个for循环提供的 k 是A矩阵的列数,B矩阵的行数

第二个问题,三个for循环这样安排有什么意义?

很明显,当计算C矩阵第一个元素的时候,即C11,需要 i 和 j 都为1,所以第一个for循环传递 i = 1 ,第二个for循环传递 j = 1。从更深层次来说,是因为C11是先有A矩阵的第1行开始,乘B矩阵的第1列,注意,是第1行,这个“行”字,所以把C的行数的循环放在最上面,可以理解为行最大吧

第二个for循环就是C矩阵的列了,除了行就是列,这个不难理解

重点是第三个for循环,很巧妙的变化了A矩阵的列数和B矩阵的行数,也是我认为这段代码中最具有艺术性的循环


我们知道,要想用代码实现一个程序或者项目,首先要设计的它的数学模型


整段代码想要实现的是两个矩阵相乘,两个矩阵相乘的概念我们在上面已经描述了,所以我们可以知道C11=A11XB11+A12XB21


从代码可以看到变化的是A的第二个元素和B的第一个元素,并且


A的第二个元素=B的第一个元素=K


所以我们可以设置一个K,并且K<=2

进行算法设计

怎么去设计这个算法?


我们知道,是通过A矩阵和B矩阵计算C矩阵,三个矩阵的行列数都是2

并且我们从概念知道C11=A11XB11+A12XB21

所以我们需要进行C11=A11XB11加C11=A12XB21

通过研究

我们发现:A的第二个元素=B的第一个元素=K

所以我们可以设计一段代码

即c[i][j]=a[i][]+b[][j]

并且设置一个K

使代码变成


c[i][j]=a[i][k]+b[k][j]

从C11=A11XB11加C11=A12XB21

可以得知要进行两次K的变换

所以设计一个for循环

for(K=1;K<=2;K++)

C矩阵一开始是0,所以设计

c[i][j]=0

我们至此已经设计完成了计算单个元素的算法

所以我们需要设计一段代码去实现C矩阵的四个元素

C的四个元素是C11,C12,C21,C22

所以我们分别设计两个for循环

去进行 i 和 j 的变换

又因为计算是先从行开始的,所以这段代码即为

for(i=1;i<=2;i++)
  for(j=1;j<=2;j++)

至此,代码设计完成。

2021年6月28日 00:06:21

希望本篇博客可以对对计算机感兴趣或者正在进行计算机学习的初学者有启发作用!

谢谢大家的赏眼!

相关文章
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
984 1
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
966 4
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树:一场数据结构与算法的华丽舞蹈,让你的程序效率飙升,直击性能巅峰!"
【8月更文挑战第20天】红黑树是自平衡二叉查找树,通过旋转和重着色保持平衡,确保高效执行插入、删除和查找操作,时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中,节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架,用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
710 1
|
存储 算法 数据管理
C语言算法复杂度
【10月更文挑战第20天】
278 5
C语言算法复杂度
|
存储 算法 程序员
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
810 7
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
1128 8
|
存储 缓存 算法
C语言在实现高效算法方面的特点与优势,包括高效性、灵活性、可移植性和底层访问能力
本文探讨了C语言在实现高效算法方面的特点与优势,包括高效性、灵活性、可移植性和底层访问能力。文章还分析了数据结构的选择与优化、算法设计的优化策略、内存管理和代码优化技巧,并通过实际案例展示了C语言在排序和图遍历算法中的高效实现。
730 2
|
机器学习/深度学习 算法 数据挖掘
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
723 1
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
874 1