数据结构 > 算法的时间复杂度(1)

简介: 数据结构 > 算法的时间复杂度(1)

1.算法效率

1.1如何衡量一个算法的好坏

如何衡量一个算法的好坏呢?比如对于以下斐波那契数列:

long long Fib(int N)
{
  if (N < 3)
    return 1;
  return Fib(N - 1) + Fib(N - 2);
}

斐波那契数列的递归实现方式非常简洁,但是简洁就一定好吗?那如何衡量其好与坏呢?

1.2算法的复杂度

算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源,因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度

时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间,在计算机发展的早期,计算机的存储容量很小,所以对空间复杂度很是在乎;但是经过计算机行业的快速发展,计算机的存储容量已经达到了很高的程度,所以我们如今已经不需要特别关注一个算法的空间复杂度

1.3复杂度在校招中的考察

校园招聘的在笔试算法题和面试中都会考察对复杂度的计算和理解

2.时间复杂度

2.1时间复杂度的概念

时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数(数学中的函数式),它定量描述了该算法的运行时间,一个算法执行所耗费的时间,从理论上来讲,是不能被算出来的,只有程序在机器上跑起来才能知道,但是上机测试很明显是有限的,所以才有了时间复杂度这个分析方式

一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度

即:找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度

我们举个例子:

估算一下Func1中++count语句总共执行了多少次?
void Func1(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\n", count);
}

我们画图分析一下

Func1执行的基本操作次数:

F(N)=N*N+2*N+10

  • N=10                F(N)=130
  • N=100              F(N)=10210
  • N=1000            F(N)=1002010

我们转化一下这个表达式,保留对它影响最大的项,即N*N

那这个表达式就变成了

F(N)=N*N

  • N=10                F(N)=100
  • N=100              F(N)=10000
  • N=1000            F(N)=1000000

我们可以看到,N越大,后两项对结果的影响越小

所以时间复杂度为:O(N^2)

2.2大O的渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为的数学符号

推导大O阶方法:

  1. 用常数1取代运行时间中的所有加法常数
  2. 在修改后的运行次数函数中,只保留最高阶项
  3. 如果最高阶项存在且不是一,则去除与这个项目相乘的常数(系数),得到的结果就是大O阶

一般情况下,时间复杂度计算时未知数都是用的N

但是也可以是其他的

注意:O(1)并不是代表代码只运行一次,而是运行常数次

2.3特殊情况

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

  • 最坏情况:任意输入规模的最大运行次数(上界)
  • 平均情况:任意输入规模的期望运行次数
  • 最好情况:任意输入规模的最小运行次数(下界)

例如:在一个长度为N的数组中搜索一个数据x

  • 最好情况:1次找到
  • 最坏情况:N次找到
  • 平均情况:N/2次找到

当一个算法随着输入不同,时间复杂度也不同,时间复杂度做悲观预期,看最坏的情况

即在这个例子中我们取O(N)

3.总结

那么今天的学习就到这里咯,今天我们学习了算法的时间复杂度的知识

小杜跟各位小伙伴在一起成长,祝我们都能成为大牛!

                                                                                                                               //小杜的成长之路

 

相关文章
|
2月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
70 1
|
2月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
82 0
|
6月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
188 10
 算法系列之数据结构-二叉树
|
6月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
157 3
 算法系列之数据结构-Huffman树
|
6月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
192 22
|
7月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
200 30
|
7月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
308 25
|
7月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
286 23
|
10月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
223 59
|
3月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
52 0
栈区的非法访问导致的死循环(x64)

热门文章

最新文章