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

动态网站开发测试题欧洲网站服务器

动态网站开发测试题,欧洲网站服务器,seo什么意思,深圳电子商城网站建设复杂度分析: 时间复杂度(算法中的基本操作的执行次数); 空间复杂度。 时间复杂度: 实际上我们计算时间复杂度时,我们其实并不需要计算准确的执行次数,只需要大概的执行次数,因此我们…

复杂度分析:

                时间复杂度(算法中的基本操作的执行次数);

                空间复杂度。

时间复杂度:

实际上我们计算时间复杂度时,我们其实并不需要计算准确的执行次数,只需要大概的执行次数,因此我们在这里使用大O的渐进表示法。常见的时间复杂度O(1), O(N²), O(N),         O(logN)。

大O符号:

是用于描述函数渐进行为的数学符号。

推导大O阶方法:

1.用常数1取代运行时间中的所有加法常数;

例:

计算下面代码的时间复杂度

void f(int N)
{int count = 0;for(int k = 0; k < 100; ++k){++count;}
}

答案:O(1)

注:确定的常数次,都是O(1)。

2.在修改后的运行次数函数中,只保留最高阶项;

例:

计算下面代码的时间复杂度

void f(int N)
{int count = 0;for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){++count;}}for (int k = 0; k < 2 * N; k++){count++;}int M = 10;while (M--){++count;}printf("%d", count);
}

答案:O(N²)

注:准确的执行次数:N² + 2 * N + 10

     随着N的增大,这个表达式中N²对结果的影响最大

3.若最高阶项存在且不是1,则去除与这个项相乘的常数。得到的结果就是大O阶。

例:

计算下面代码的时间复杂度

void f(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){count++;}int M = 10;while (M--){++count;}printf("%d", count);
}

答案:O(N)

特殊情况:

例一:

计算下面代码的时间复杂度

void f(int N, int M)
{int count = 0;for (int k = 0; k < N; k++){++count;}for (int k = 0; k < M; k++){++count;}
}

答案:O(M + N)

注:假如给了条件:M远大于N,答案是O(M);M和N差不多大,O(M)或O(N)。

例二:

计算下面代码的时间复杂度

const char* s(const char* str, char cha)
{while (*str != '\0'){if (*str == cha){return str;}++str;}return NULL;
}

假设字符串长度是N。

答案:O(N)

注:有些算法的时间复杂度存在最好,平均,最坏情况:

        最坏:O(N)

        平均:O(N/2)

        最好:O(1)

在实际中一般情况关注的是算法的最坏运行情况。

例三:

计算下面代码的时间复杂度

void B(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (!exchange){break;}}
}

答案:O(N²)

注:第一趟冒泡:N

       第二趟冒泡:N - 1

       ........ 

      第N趟:1

以上是个等差数列,所以准确的次数是(N+1)*N/2

时间复杂度为O(N²)

例四:

计算下面代码的时间复杂度

int B(int* a, int n, int x)
{assert(a);int begin = 0;int end = n;while (begin < end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x){begin = mid + 1;}else if (a[mid] > x){end = mid;}else{return mid;}}return - 1;
}

答案:O(logN)

注:假设找了X次

2的X的平方 = N

X=logN

因为有很多地方不好写底数,所以一般省略简写成logN。 

例五:

计算下面代码的时间复杂度

long long f(size_t N)
{return N < 2 ? N : f(N - 1) * N;
}

答案:O(N²)

注:递归调用了N次,每次递归运算--》O(1)

整体就是O(N)。

http://www.mmbaike.com/news/96215.html

相关文章:

  • 在线网站制作百度收录提交入口网址是什么
  • iis上做的网站外网怎么访问广告发布
  • 设计师看什么网站百度竞价和优化的区别
  • 苏州市城乡建设档案馆网站论坛seo网站
  • 台湾网站域名竞价代运营公司
  • 什么网站可以做期货seo网络推广外包公司
  • 古腾堡wordpress唐山seo
  • 惠州市网站开发互联网广告优势
  • 广告页面设计软件百度 seo 工具
  • 做b2b网站用什么架构品牌推广方案怎么写
  • wordpress图片切换seo竞价推广
  • 建https网站百度推广关键词价格查询
  • php开发网站项目心得建站abc
  • 电商设计师网站企业seo推广
  • 网站上全景云台怎么做的营销网络营销
  • 彩票源码网站的建设浏览器2345网址导航下载安装
  • 英国做网站的人网络营销品牌推广公司
  • 营销网络建设怎么写东莞网站推广行者seo08
  • 宁波企业网站排名优化公司网站友情链接自动上链
  • 做的网站老被攻击成都网站排名生客seo怎么样
  • 网站建设云梦推广引流网站
  • 怎么创建一个公司网站抖音广告推广怎么收费
  • 36氪网站是用什么做的seo是什么姓
  • 网站运营与建设 教学大纲西点培训
  • 网站用户注册怎么建推广优化seo
  • 桂林网站艰涩河北百度推广
  • wordpress 微视频主题蜘蛛seo超级外链工具
  • 网站限定域名南宁市优化网站公司
  • 企业官方网站建设教程天津百度推广
  • 无锡网站建设哪里好推广下载app赚钱