前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >时间复杂度

时间复杂度

作者头像
晚上没宵夜
发布2022-05-09 21:00:22
3790
发布2022-05-09 21:00:22
举报
文章被收录于专栏:Howl同学的学习笔记

在了解时间复杂度之前,先了解一下原操作和时间频度


一.原操作

原操作是指固有的数据类型的操作,可以理解为基本运算,下面的代码块中 3,6,7,9 都是原操作

代码语言:javascript
复制
例1
1. void foo (int a[],int n)
2. {
3.    int i;
4.    for(i = 0;i < n;i++)
5.    {
6.        a[i] = i + 1;
7.        printf("%d",a[i]);
8.    }
9.    printf("\n");
10.}
二.时间频度 T(n)

时间频度是该算法所有原操作的执行次数,它是问题规模n的函数,用T(n)表示.下面采用简化方法去分析,即只考虑算法内最深层循环内的原操作

代码语言:javascript
复制
例2
void foo (int n)
{
    int i,j;
    for(i = 0;i < n;i++)                     //循环n次
    {
        for(j = 0;j < n+10;i++)				 //循环n+10次
        {
            printf("%d",i+j);                //即深层原操作次数为n^2+10n
        }
    }
}

即 T(n) = n^2+10n

三.时间复杂度 O(n)

时间复杂度是用时间频度的最大数量级表示: O(n) = ( T(n)的数量级 )

例2中,T(n) = n^2+10n,其最大数量级为 n^2 (即忽略其常数和低级次幂)

最后 O(n) = n^2

四.时间复杂度对照表

O(1) < O(log2 N) < O(n) < O(nlog2 N) < O(n^2) < O(n^3) < O(2^n) < O(n!)

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-10-25,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一.原操作
  • 二.时间频度 T(n)
  • 三.时间复杂度 O(n)
  • 四.时间复杂度对照表
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档