什么是算法

发表于 分类于 阅读次数：

算法：

  • 算法是模型分析的一组可行的、确定的和有穷的规则（广泛）
  • 算法是解决实际问题的一种精确的描述方法
  • 算法是对特定问题的求解步骤的一种精确描述方法

算法的特性

  • 有穷性：算法的指令或者执行步骤是有限的
  • 确切的：算法的每一个指令和步骤都必须有明确的定义和描述
  • 输入：一个算法应该有的输入条件，用于初始化
  • 输出：一个算法应该有个名明确的结果输出
  • 可行性：执行步骤的可行，且有可以在有限时间内完成

算法分类

  • 按照应用来分类
    • 基础算法、数据结构、几何、加密、查询、排序等等
  • 按照确定性来分类
    • 确定性算法：有限时间内完成，结果唯一
    • 非确定性算法：有限时间内完成，结果往往不唯一
  • 按照算法思路
    • 递推、递归、穷举、贪婪、分治、动态规划、迭代等算法

算法概念

  • 数据结构+算法+程序设计语言 = 程序
  • 数据结构表示处理对象，算法是计算和处理的核心方法，程序设计语言是算法的实现方法。这几者综合便构成了一个程序

算法的表示

  • 自然语言表示
  • 流程图
  • N-S图
  • 伪代码表示

算法性能评价

  • 时间复杂度：算法执行所消耗的时间，时间越短，性能越好,算法越好。
    • 与每条语句执行的数量有关
    • 与问题的规模有关
  • 空间复杂度：算法执行所消耗的存储空间，消耗越小，算法越好。
    • 程序保存所需要的存储空间，程序的大小
    • 程序执行过程中所需消耗的存储空间（变量等）

算法实例

一个班级学生档案集中查找某一个学生的档案
伪代码

1
2
3
4
5
6
7
8
9
10
变量 x = 输入需要查找的数据
变量 arr = 随机生产数组数据
for 1到20{
    if(arr[i] ==){
    找到数据
    break;
    }
}
输出该数据的位置
程序结束

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public Class Test1{
    static int N = 20;
    public static void main(String args[]){
    int arr[] = new int[N];
    int x;
    int pos = -1;
    Random r= new Random();
    for(int i=0; i<N; i++){
        arr[i] = r.nextInt(100);
    }
    System.out.println("生成随机数序列")
    for(int i=0; i<N; i++){
        System.out.print(arr[i]+" ");
    }

    System.out.print("输入要查找的整数");
    Scanner input = new Scanner(System.in);
    x = input.getInt();
    for(int i=0; i<N; i++){
        if(arr[i] == x){
            pos = i;
            break;
        }
    }

    if(f<0){
        System.out.print("未找到数据");
    }else{
        System.out.print(x+"数据位于"+pos+"位置，是数组的第"+(pos+1)+"个元素");
    }
    } 
}