当前位置: 首页 > news >正文

南皮做网站网站优化推广招聘

南皮做网站,网站优化推广招聘,网站建设金手指15,苏州网站建设招聘文章目录 时间复杂度常数阶时间O(1)对数阶时间O(logN)线性阶时间O(n)线性对数阶时间O(nlogN)平方阶时间O(n*n) 空间复杂度常量空间O(1)线性空间O(n)二维空间O(n*n)递归空间 时间复杂度 常数阶时间O(1) 代码在执行的时候,它消耗的时间并不随着某个变量的增长而增长…

文章目录

  • 时间复杂度
    • 常数阶时间O(1)
    • 对数阶时间O(logN)
    • 线性阶时间O(n)
    • 线性对数阶时间O(nlogN)
    • 平方阶时间O(n*n)
  • 空间复杂度
    • 常量空间O(1)
    • 线性空间O(n)
    • 二维空间O(n*n)
    • 递归空间

时间复杂度

常数阶时间O(1)

  • 代码在执行的时候,它消耗的时间并不随着某个变量的增长而增长,那么无论这类代码有多长,都可以用O(1)来表示它的时间复杂度
  • 我们知道常数项对函数的增长速度影响不大,所以当T(n)=C,C为一个常数的时候,我们说这个算法的时间复杂度为O(1);如果T(n)不等于一个常数项时,直接将常数项省略。
int i=1;
int j=2;
++i;
j++;
int m=i+j;

对数阶时间O(logN)

  • 在while循环里面,每次都将i乘以2,乘完之后,i距离n就越来越近了。我们试着求解一下,假设循环x次之后,i就大于n了,此时这个循环就退出了,也就是说2的x次方等于n,那么x=n
int i=1;
while(i<n)
{
i=i*2;
}

线性阶时间O(n)

  • for循环里面的代码会执行n遍,因此它消耗的时间是随着n的变化而变化的
  • 如果T(n)不等于一个常数项时,直接将常数项省略。因为函数的阶数对函数的增长速度的影响是最显著的,所以我们忽略与最高阶相乘的常数.
  • 我们知道高次项对于函数的增长速度的影响是最大的,同时因为要求的精度不高,所以我们直接忽略低次项。或者说:如果复杂度是多个n的函数之和,则只关心随n的增长而增长得最快的那个函数。
int aFunc(int n){for(int i=0;i<n;i++){             //n+1次printf("Hello,World!\n");     //n次}return 0;                         //1次
}

这个代码需要(n+1+n+1)=2n+2次运算,时间复杂度为O(n)

线性对数阶时间O(nlogN)

  • 将时间复杂度为O(logN)的代码循环n遍的话,那么它的时间复杂度就是n*O(logN),也就是O(nlogN)
for(m=1;m<n;m++){int i=1;while(i<n){i=i*2;}
}

平方阶时间O(n*n)

  • 如果把O(n)的代码再嵌套循环一遍,它的时间复杂度就是O()
  • 如果将其中一层循环的n改成m那它的时间复杂度就变成O(m*n)
for(x=1;i<=n;x++){for(i=1;i<=n;i++){j=i;j++;}
}

【例1】N×N矩阵相乘

for(i=1;i<=n;i++)                          //n+1for(j=1;j<=n;j++){                     //n*(n+1)c[i][j]=0;                         //n*nfor(k=1;k<=n;k++)                  //n*n*(n+1)c[i][j]=c[i][j]+a[i][k]*b[k][j];//T(n)=O(n*n*n)}
  • 级数求和的方式去算

【例2】

for(i=1;i<=n;i++)for(j=1;j<=1;j++)for(k=1;k<=j;k++)x=x+1;

【例3】分析以下程序的时间复杂度

i=1;
while(i<=n)i=i*2;

关键是要找出来执行次数x与n的关系,并完成n的函数。

  • 若循环执行1次:i=1*2=2
  • 若循环执行2次:i=2*2=2^2
  • 若循环执行3次:i=22*2=23,……
  • 若循环执行x次:i=2^x

设语句i=i*2执行次数为x次,由循环条件i<=n,所以2^x<=n,所以x<=log以2为底n

即f(n)<=log以2为底n,取最大值f(n)=log以2为底n

空间复杂度

常量空间O(1)

  • 如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为O(1)
int i=1;
int j=2;
++i;
j++;
int m=i+j;

线性空间O(n)

  • 这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间。因此,这段代码的空间复杂度主要看第一行即可,即S(n)=O(n)
int[] m=new int[n];
for(i=1;i<=n;++i)
{j=i;j++;
}

【例】将一维数组a中的n个数逆序存放到原数组中。

【算法1】交换数组a中每一个位置的值
for(i=0;i<n/2;i++){t=a[i];         //创建辅助空间t,变量t与n是多少没有关系.S(n)=O(1)a[i]=a[n-i-1];a[n-i-1]=t;
}
【算法2】将a中所有元素依次倒着放入b数组
for(i=0;i<n;i++)b[i]=a[n-i-1]; //创建辅助数组b,b的大小和数组a的大小一样,S(n)=O(n)
for(i=0;i<n;i++)a[i]=b[i];

二维空间O(n*n)

当算法分配的空间是一个二维数组集合,并且集合的长度和宽度都与输入规模n成正比时,空间复杂度记作O()

int[][] matrix=new int[n][n];//O(n^2)
int[][] matrix=new int[m][n];//O(mn)

递归空间

正如下面代码一样,递归代码中没有显示声明变量或者集合,但是计算机在执行程序时,会专门分配一块内存,用来存储“方法调用栈”。

void fun4(int n){if(n<=1){return;}fun4(n-1);...
}

方法调用栈包括入栈和出栈两个操作:

当进入一个新方法时,执行入栈操作,把调用的方法和参数信息压入栈中

当方法返回时,执行出栈操作,把调用的方法和参数信息从栈中弹出

还是上述代码,假设现在传入参数5,那么方法fun4(5)的调用信息先入栈:

method fun4

n 5

接下来递归调用相同的方法,方法fun4(4)的调用信息入栈:

method fun4

n 4

method fun4

n 5

以此类推,递归越来越深,栈内的元素也越来越多,最终:

method fun4

n 1

method fun4

n 2

method fun4

n 3

method fun4

n 4

method fun4

n 5

当n=1的时候,触发递归的结束条件,执行return,方法出栈。最终所有入栈的元素都会出栈。

由上面“方法调用栈”的出入栈过程可以看出,执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的,如果递归的深度是n,那么空间复杂度就是O(n).

http://www.dt0577.cn/news/204.html

相关文章:

  • 电商网站开发流程代码seo研究中心
  • 福州网络公司网站软文推广案例
  • 外国游戏概念设计网站百度在线咨询
  • 用网站做淘客怎么赚钱线上推广方案怎么写
  • 全国做临期进口食品的网站短信营销
  • 做一个独立站需要多少钱附近电商培训班
  • 网站服务器是网站的空间吗软文营销的技巧有哪些
  • 周口建设局网站互联网推广话术
  • 手机管理网站做推广的公司
  • 电子商务网站运营与管理谷歌推广外贸建站
  • 南通做网络网站旅游app推广营销策略
  • 福田专业网站建设公司seo1新地址在哪里
  • 网站建设柒金手指花总15外贸网站谷歌seo
  • 用asp做网站流程游戏推广员好做吗
  • 用JSP做电商网站百度搜索引擎优化怎么做
  • 网站建设后期需要后期做的刷网站软件
  • 建设淘宝网站的市场分析seo 推广怎么做
  • 怎样做diy家具网站微信管理软件
  • 唐山的做网站的企业注册网站查询
  • 化妆品网站建设操作可行性分析旺道网站优化
  • 建设网站物业经理上岗证陈俊华百度指数分析大数据
  • 百度开放云搭建网站网站是如何建立的
  • seo网站优化插件排名优化公司哪家好
  • 简述电子政务网站设计的技术拓客平台有哪些
  • 新加坡网站建设公司在线收录
  • 东莞疫情最新消息今天seo网站排名推广
  • 利用网站制作网页快照网站
  • 宁夏网站建设电话武汉网站关键词推广
  • 旧房翻新装修百度seo优化方案
  • 公司网站建设意见和建议推56论坛