算法分析课堂内容补充及补分博客

课堂内容:简述算法复杂度的基本概念,分析在不同情况下算法复杂度的计算方法,以及对增长函数的分析。首先对算法分析进行了简述,算法是一组有的规则,它们规定了解决某一特定类型问题的一系列运算,是对解题方案内的准确与完整地描述。制定一个算法,一般要经过设计、确认、分析、编码、测试、调试、计时等阶段。而对于函数计算方法,需要引入算法的阶以及复杂度,大O符号即可表示算法的阶,引入数学符号“O”来估算算法时间复杂度,渐进时间复杂度的表示方法:F(n)=O(g(n)),其定义为,若F(n)和g(n)是定义在正整数集合上的两个函数,则F(n)=O(g(n))表示存在正的常数C和 ,使得当 时,都满足 。换句话说,就是这两个函数当整形自变量n趋于无穷大时,两者的比值是一个不等于0的常数。
同时在计算算法复杂度时,要学会一些常见的计算方法,如在计算常见的渐进时间复杂度时,有
对于算法复杂度,是指算法在编写成可执行程序后,运行时所需要的资源,资源包括时间资源和内存资源。对于线性的规则,常数阶O(1),对数阶O(log2n)(以2为底n的对数,下同),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),...,k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。举一个以n阶方阵的实例:
在这个算法中,T(n)=2n3+3n2+2n+1 (1.1)为所有语句的频度之和(即算法的时间耗费)。即可得出O(n^3)。
课堂练习:
1.
这题相对比较基础,同时输入x和y,并且在运算结束后会返回y值,先分析算式可得复杂度为n,由于当n大于1时,循环才会开始,且输入为n,每次为n--,所以会循环n-1次。
2.
第二题的难度就相对较大,考察到了对算法复杂度的理解情况和对代码的分析能力,其中第一题还是比较常规,当i小于n时,进行循环,且运算的实践复杂度为n。比较需要思考和推导的是第三题,第三题需要分析算法函数,也需要化简算法。因为i和s在开始都输入0,可以先设n为一个具体的数,可推出O(n^2)的复杂度为n,则其实际复杂度为根号n。在举过特例后在对式子进行化简,可以得到相同的结果。
课下补充练习:
补充练习需要实际的代码来实现。
#include <stdio.h>

define ARRAY_LEN 1000 //length

void createArr (int* arr, int len) {
// put in
int i;
for (i = 0; i<len; i++)
scanf("%d",&arr[i]);
}

int arrSum (int* arr, int len) {
// 求和
int i = 0, sum = 0;
for (i = 0; i<len; i++)
sum += arr[i];
return sum;
}

int main(void) {
int len,arr[ARRAY_LEN];

printf("put in the length : ");
scanf("%d",&len);
printf ("============ ");

printf("请输入数组内容,共%d个元素: ",len);
createArr (arr , len);
printf ("============ ");

printf("数组所有元素之和为: %d",arrSum (arr, len));
printf (" ");

return 0;
}
这个算法可以简单的对给定元素进行累加,当输入n后开始循环,是一个求和算法。对第一个条件,在一维算法进行累加则为O(n)。
第二个算法需要对已有的数组进行排序,这个是很基础的排序算法。
for (int i = 0; i < array.length; i++) {//array为数组
    for (int j = 0; j < i; j++) {
        if(array[i] < array[j]){
            int temp = array[i];
        array[i] = s[j];
        array[j] = temp;
    }
}
这是一个插入排序算法,可以对应课本内容。

import javax.swing.JOptionPane;
public class Arrange{
public static void main (String args[]){
String str;
int x,y,z;
int temp;
str=JOptionPane.showInputDialog("第一个数");
x=Integer.parseInt (str);
str=JOptionPane.showInputDialog("第二个数");
y=Integer.parseInt (str);
str=JOptionPane.showInputDialog("第三个数");
z=Integer.parseInt (str);

if(x>y) {
temp = y;
y = x;
x = temp;
}

if(y>z){
temp = y;
y = z;
z = temp;
}
if(x>y){
temp = y;
y = x;
x = temp;
}

System.out.println("从小到大排列="+x+" "+y+" "+z);

}
}
除去插入排序的方法,可以得到常规排序的结果。

原文地址:https://www.cnblogs.com/Metwox/p/7586795.html