云南省火电建设公司网站,沈阳市网站设计制作公司,建设工程施工合同解除,双语网站系统文章目录 前言计算机重要存储数据结构与算法数据结构概念算法 数据库概念 算法的复杂度时间复杂度概念为什么有时间复杂度大O渐进表示法时间复杂度实例实例1#xff1a;时间复杂度#xff1a;O#xff08;N#xff09;实例2#xff1a;这里输入参数是不确定的所以 时间复杂… 文章目录 前言计算机重要存储数据结构与算法数据结构概念算法 数据库概念 算法的复杂度时间复杂度概念为什么有时间复杂度大O渐进表示法时间复杂度实例实例1时间复杂度ON实例2这里输入参数是不确定的所以 时间复杂度为OMN 前言
计算机重要存储 重要存储分为俩种内存和硬盘
数据结构与算法
数据结构概念 数据结构(Data Structure)是计算机存储、组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合。 *简述 对内存进行数据管理
算法 算法(Algorithm):就是定义良好的计算过程他取一个或一组的值为输入并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。 简述
对数据进行处理
数据库
概念
*简述 对硬盘进行数据管理
算法的复杂度 算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源。 因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。 时间复杂度
概念 时间复杂度的定义在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。 即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。
为什么有时间复杂度 时间复杂度能让我们了解当前思路的执行程序次数。 当一个问题拥有几个解决的思路算出解决思路的时间复杂度可知最优的解决思路 大O渐进表示法
大O渐进表示法 是用于描述函数渐进行为的数学符号。 估算出来的时间复杂度 推导大O阶方法 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。 有些时间复杂度分为多种情况例如 最好 - 平均 - 最坏 能让算法的时间复杂度在预估计的执行范围内 时间复杂度实例
实例1时间复杂度ON
// 计算Func2的时间复杂度
void Func2(int N)
{int count 0;for (int k 0; k 2 * N ; k) 这里执行2N次{count;}int M 10;while (M--) 执行10次{count;}printf(%d\n, count);
}
实例2这里输入参数是不确定的所以 时间复杂度为OMN
void Func3(int N, int M)
{int count 0;for (int k 0; k M; k) 执行M次{count;}for (int k 0; k N ; k) N次{count;}printf(%d\n, count);}实例3输入参数与执行次数无关 执行常数次 所以是 O1
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}实例4 这里从一个字符串中寻找一个字符 寻找的情况分为 最好1-前几个找到 平均在中间前后范围找到 最坏最后一找到 or 没有找到 时间复杂度取最坏情况:所以是ON
// 计算strchr的时间复杂度
const char * strchr ( const char * str, int character );
{while(*str){if(*strcharacter)return str;elsestr;}}
实例5: 计算时间复杂度最好是按思路计算 数循环不能正确算出所有的时间复杂度 冒泡排序的思想按升序排序前后交换前后前后一直到最后排序最大的接着排出次大的排序执行次数n-1 n-2 ------ 2 1 这是一个等差数列计算出和就是执行次数 为((1n-1)*(n))/2 时间复杂度O(N^2)
int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n-1;// [begin, end]begin和end是左闭右闭区间因此有号while (begin end){int mid begin ((end-begin)1);if (a[mid] x)begin mid1;else if (a[mid] x)end mid-1;elsereturn mid;}return -1;
}
