算法复杂度分析_o(log10n)=o(log2n)-程序员宅基地

技术标签：算法时间复杂度

设计一个算法，一定要考虑到它的复杂度（空间、时间），那么，接下来，我们一步步来学习怎样分析一个算法的复杂度。

一、数据规模

首先，我们要清楚设计这个算法是要处理什么规模的数据的，根据处理的数据的规模，从而设计出适合的算法。

通常，如果要想在 1s 之内解决问题：

O(n^2) 的算法可处理约 10^4 级别的数据
O(n) 的算法可处理约 10^8 级别的数据
O(nlogn) 的算法可处理约 10^7 级别的数据

不过在实际情况中，保险起见，可以对数量级低估一点，除以 10 或者除以 2，这样就比较保险了。

二、空间复杂度

常见的空间复杂度就不解释了，需要说明的是一种比较特殊的情况。

递归是比较常见的一种算法思路，但递归调用是有空间代价的，因为计算机要把递归之前的数据压入栈中，会占用一定的空间，这点我们需要特别注意。

空间复杂度 O(1)

    public static int sum1(int n) {
        int ret = 0;
        for (int i = 0; i <= n; i++) {
            ret += i;
        }
        return ret;
    }

这是一个简单求和的一个函数，我们只开了一个 ret 存放返回结果，和一个索引 i 的值，所以空间复杂度就是 O(n) ，不过我们也可以用递归来写，但是这样空间复杂度就变了。

空间复杂度 O(n)

    public static int sum2(int n) {
        if (n == 0)
            return 0;

        return n + sum2(n - 1);
    }

这是因为在计算从 0 到 n 这些数的和，需要递归调用的深度是 n，栈中需要装载 n 个状态，也就是空间复杂度为 O(n)。

因此，在设计算法时，如果用到了递归，需要小心，不要让你的递归看起来聪明，但实际上性能却很差。

三、常见的时间复杂度分析

接下来，我们通过常见的一些函数来具体分析一下他们的时间复杂度。

注意，下面这些例子中，我们暂且假设输入都是合法输入，这样方便我们突出重点，但是在实际的算法设计中，是需要考虑到合法输入、边界条件等等信息的。

1. O(1)

e.g. 交换

    private</

本文链接：https://blog.csdn.net/lixibin0829/article/details/80114407

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

工具：PsTools-windows问题定位系列小工具-程序员宅基地

文章浏览阅读2.4k次，点赞2次，收藏7次。PsTools是Sysinternals Suite中一款排名靠前的一个安全管理工具套件。现在被微软收购。目前pstools中含各式各样的小工具。如果将它们灵活的运用，将会在渗透中收到奇效。所有的pstool第一次运行时都会弹框。可以用–accepteula这个参数绕过。_pstools

linux环境下questasim 10.7的安装总结_linux安装questa sim-程序员宅基地

文章浏览阅读5.4k次，点赞4次，收藏29次。reference: https://blog.csdn.net/weixin_36590806/article/details/109692507https://centos.pkgs.org/https://blog.csdn.net/weixin_36590806/article/details/109692507https://blog.csdn.net/weixin_34326558/article/details/90072161http://www.myir-tech.com/faq__linux安装questa sim

Jenkins邮件推送配置_jenkins foxmail邮件推送-程序员宅基地

文章浏览阅读1.4k次，点赞26次，收藏6次。注意认证的邮箱密码不是QQ密码而是授权码，初次设置（如果使用手机号验证）的话需要花3毛钱发送短信到腾讯进行认证才能设置，按提示操作即可。温馨提醒：为了你的帐户安全，请不要告诉他人你的授权码，更改QQ帐号密码会触发授权码过期，需要重新获取新的授权码登录。勾选：【通过发送测试邮件测试配置】，然后填入接收测试邮件的邮箱，点击【Test configuration】按钮。注意Job中配置的内容会覆盖之前system中的配置，如果缺省的话就使用system中的配置。pop.qq.com，使用SSL，端口号995。_jenkins foxmail邮件推送

文件上传下载篇（前端JSP，后端SSM），注解多多，简单明了，复制就能用。（内含源码）_jsp传到ssm-程序员宅基地

文章浏览阅读2.6w次，点赞34次，收藏65次。Echarts之柱状图动态加载数据篇我搭建好的环境，有兴趣的小伙伴可以运行看下效果（里面还有饼状图和柱状图的实现）老规矩，先上效果：前台代码：<%@ page language="java" contentType="text/html; charset=UTF-8" pageEncoding="UTF-8" %><%@ taglib p..._jsp传到ssm

00000000000000000000000-程序员宅基地

文章浏览阅读819次。111事实生生死死生生死死生生死死_00000000000000000000000

Apollo自动驾驶系统概述（文末参与活动赠送百度周边）_apollo智能驾驶介绍-程序员宅基地

文章浏览阅读560次，点赞5次，收藏2次。参与活动领取奖励_apollo智能驾驶介绍