算法的基本概念

作者: 暮想sun | 来源:发表于2019-12-16 21:04 被阅读0次

算法:

解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令标识一个或多个操作。

算法的特性:

1.输入输出:具有零个或多个输入。至少有一个或多个输出。
2.有穷性:算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每个步骤在可接受的时间内完成。
3.确定性:每一步骤都具有确定的含义,不会出现二义性。
4.可行性:每一步都能通过执行有限次数完成。

算法设计的要求:

1.正确性:至少具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
2.可读性:为了便于阅读、理解和交流。
3.健壮性:当输入数据不合法时,也能做出相关处理,而不处产生异常或莫名其妙的结果。
4.时间效率高和存储量低

算法的时间复杂度:

在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。
T(n)=O(f(n)) 表示岁问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度。
f(n)是问题规模n的某个函数。

推导大O阶:

1.用常数1取代运行时间中的所有加法常数。
2.只保留最高项。
3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。

最好时间复杂度:在最理想的情况下,执行这段代码的时间复杂度。
最坏时间复杂度:在最糟糕的情况下,执行这段代码的时间复杂度。
平均时间复杂度:

加权平均时间复杂度或者期望时间复杂度。

均摊时间复杂度:

每一次 O(n) 的插入操作,都会跟着 n-1 次 O(1) 的插入操作,所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上,均摊下来,这一组连续的操作的均摊时间复杂度就是 O(1)。


 // array表示一个长度为n的数组
 // 代码中的array.length就等于n
 int[] array = new int[n];
 int count = 0;
 
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

相关文章

  • 数据结构学习大纲

    第一章 绪论 数据结构基本概念数据结构基本概念算法的基本概念算法的时间复杂度与空间复杂度分析基础时间复杂度分析空间...

  • 《数据结构》第一章:数据结构基本概念

    数据结构:用程序代码把现实世界的问题信息化 1.1数据结构的基本概念 1.2.1算法的基本概念 1.2.3算法的空...

  • 2018考研数据结构复习

    一、概述 1.数据的逻辑结构与存储结构的基本概念;2.算法的定义、基本性质以及算法分析的基本概念,包括采用大O形式...

  • 【weka应用技术与实践】【数据挖掘】举例说明Kmeans算法的

    源自:K-means 算法【基本概念篇】 1. Kmeans算法的认识 k均值聚类算法(k-means clust...

  • [数据结构]第一章绪论(2)——算法

    绪论第二节——算法 基本概念 什么是算法? 程序=数据结构+算法 算法的特性 有穷性:一个算法必须总在执行有穷步之...

  • 数据结构和算法:什么是数据结构和算法

    程序 = 算法 + 数据结构 一、算法 1. 基本概念 计算机科学中的算法指的就是计算机执行的指令。 算法是计算机...

  • 算法的基本概念

    算法: 解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令标识一个或多个操作。 算法的特性:...

  • 算法的基本概念

    1.算法: 算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操...

  • 算法:基本概念

    什么是算法? 算法解决某个特定问题步骤的描述。 算法的特性 输入:可以是零个或者多个输入。 输出:可以是一个或者多...

  • 一、STL理论基础

    学习重点 STL基本概念 理解容器的概念 理解迭代器的概念 理解算法的概念 1.STL基本概念 STL(Stand...

网友评论

    本文标题:算法的基本概念

    本文链接:https://www.haomeiwen.com/subject/nqxjnctx.html