首页 > 编程语言 >算法衡量优劣之时间复杂度

算法衡量优劣之时间复杂度

时间:2023-09-05 23:44:06浏览次数:34  
标签:优劣 复杂度 算法 时间 pythagorean time find

 

选型

我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位 , 那么有多少个基本操作就代表会花费多少时间单位 , 由此可以忽略机器环境的影响而客观的反应算法的时间效率

代码执行总时间(T) = 操作步骤数量 * 操作步骤执行时间

 

算法时间复杂度是用来描述算法在运行时所需的时间资源的度量。它通常表示为一个函数,该函数描述了算法的运行时间与输入规模之间的关系

时间复杂度是分析算法性能的重要工具,它可以帮助我们比较不同算法的效率,以便在解决问题时选择最优算法。

时间复杂度通常使用大O符号(O)来表示,以下是一些常见的时间复杂度:

  1. O(1) - 常数时间复杂度:算法的运行时间与输入规模无关,即使输入规模增加,运行时间也保持不变。例如,访问数组的某个元素(通过索引访问)。

    • 示例: 访问数组中的元素、插入或删除链表的头节点。
    • 最佳实践: 常数时间复杂度是最理想的情况,尽量选择常数时间的算法。
  2. O(log n) - 对数时间复杂度:算法的运行时间与输入规模的对数成正比。典型示例是二分查找。

    • 示例: 二分查找、某些分治算法。
    • 最佳实践: 对数时间复杂度通常表示算法在大规模数据上具有很好的性能,尤其在搜索和排序问题上。
  3. O(n) - 线性时间复杂度:算法的运行时间与输入规模成线性关系。例如,遍历数组中的所有元素。

    • 示例: 遍历数组、查找未排序的数组中的元素。
    • 最佳实践: 线性时间复杂度是一种常见的时间复杂度,通常是一个合理的选择。但对于某些问题,可能需要更高效的算法。
  4. O(n log n) - 线性对数时间复杂度:算法的运行时间与输入规模的线性关系乘以对数。典型示例是快速排序和归并排序。

    • 示例: 快速排序、归并排序、某些高效的搜索算法。
    • 最佳实践: 线性对数时间复杂度通常是排序问题的最佳选择,它在大规模数据上表现出色。
  5. O(n^2) - 平方时间复杂度:算法的运行时间与输入规模的平方成正比。例如,嵌套循环遍历二维数组。

    • 示例: 冒泡排序、插入排序、某些矩阵运算。
    • 最佳实践: 平方时间复杂度通常在大规模问题上表现较差,尽量避免使用,除非输入规模非常小。
  6. O(n^k) - 多项式时间复杂度:算法的运行时间与输入规模的幂次成正比,其中k是常数。例如,一些多项式时间复杂度的动态规划算法。

    • 示例: 某些动态规划算法。
    • 最佳实践: 多项式时间复杂度通常在问题的解空间较大时表现较好,但需要权衡计算时间和内存消耗。
  7. O(2^n) - 指数时间复杂度:算法的运行时间与输入规模的指数成正比。典型示例是解决旅行推销员问题的暴力搜索。

    • 示例: 旅行推销员问题的穷举法解法。
    • 最佳实践: 指数时间复杂度通常在大规模问题上不可接受,需要寻找更高效的算法。
  8. O(n!) - 阶乘时间复杂度:算法的运行时间与输入规模的阶乘成正比。典型示例是解决旅行推销员问题的穷举法。

    • 示例: 旅行推销员问题的穷举法解法。
    • 最佳实践: 阶乘时间复杂度通常在实际问题中不可接受,需要考虑其他解决方案。

最佳实践:

  1. 问题分析: 在选择时间复杂度时,首先仔细分析问题的性质和输入规模,以确定哪种时间复杂度最合适。

  2.  选择合适的数据结构: 选择适合问题的数据结构可以显著影响算法的时间复杂度。例如,对于查找操作,哈希表通常比线性搜索更快。
  3. 选择经典算法: 考虑使用已知的高效算法,避免自行实现复杂的算法,除非必要。特别是在问题领域已经有成熟的解决方案时。

  4. 性能测试: 对不同时间复杂度的算法进行性能测试,以确定哪种算法在实际应用中表现最佳。

  5. 优化: 对于高时间复杂度的算法,考虑优化方案,例如使用更快的数据结构、剪枝、并行化等。

  6.  避免不必要的操作: 精简算法以减少不必要的操作,以降低时间复杂度。考虑是否可以剪枝、合并循环等。
  7. 平衡: 在选择时间复杂度时,需要平衡算法的运行时间和内存消耗。有时候,降低时间复杂度可能会导致更高的内存使用。

  8. 维护和测试: 定期维护和测试算法,确保它在不同场景下仍然高效。

  9.  分析和测试: 对算法进行时间复杂度分析,并进行实际测试来验证性能。确保算法在不同规模的输入下都能有效运行。

示例: 让我们看一个示例,计算前n个自然数的和的算法,并分析它的时间复杂度。

1 def sum_of_n_natural_numbers(n):
2     total = 0
3     for i in range(1, n + 1):
4         total += i
5     return total

坑:

  1. 忽略常数因子: 时间复杂度分析通常忽略常数因子。因此,O(2n) 和 O(n) 在大规模问题上被认为是相同的。

  2. 不同情况下的时间复杂度: 算法的时间复杂度可能在不同情况下有所不同,例如最佳情况、最坏情况和平均情况。需要考虑这些情况来全面评估算法性能。

  3. 空间复杂度: 时间复杂度只关注运行时间,而不考虑内存消耗。要考虑算法的空间复杂度,特别是对于内存有限的环境。

优化

以一个题目讲解时间复杂度的优化:    选型: 使用穷尽法。在此选型的基础上做代码优化(题目分析 + 用对数据结构 + 减少遍历 + 数学基础)

如果 a+b+c=1000,且 a^2+b^2=c^2(a,b,c 为自然数),如何求出所有a、b、c可能的组合?

 方法1:直接穷举法(不伤脑)

import time

'''
方法一:穷举法
这是一种最简单的方法,它穷尽了所有可能的自然数三元组,检查是否满足条件。
'''


def find_pythagorean_triplets01(n):
    triplets = []  # 定义一个列表存放满足条件的结果
    n = n + 1
    for a in range(0, n):
        for b in range(0, n):  # 因为自然数是包括0的
            for c in range(0, n):
                if a ** 2 + b ** 2 == c ** 2 and (a + b + c == n - 1):
                    triplets.append((a, b, c))
    return triplets


def find_pythagorean_triplets02(n):
    triplets = []
    n = n + 1
    for a in range(1, n):
        for b in range(a, n):
            c = n-1 - a - b
            if a ** 2 + b ** 2 == c ** 2:
                triplets.append((a, b, c))
    return triplets


# 记录开始时间
start_time = time.time()
triplets = find_pythagorean_triplets01(1000)
# 记录结束时间
end_time = time.time()
# 计算执行时间
execution_time = end_time - start_time
# 打印执行时间
print(f"find_pythagorean_triplets01方法执行时间: {execution_time} 秒")
print(f"find_pythagorean_triplets01方法执行结果:{triplets}")

 输出结果:

find_pythagorean_triplets01方法执行时间: 107.37241101264954 秒
find_pythagorean_triplets01方法执行结果:[(0, 500, 500), (200, 375, 425), (375, 200, 425), (500, 0, 500)]

  

方法2:优化的穷举法

 1 import time
 2 
 3 def find_pythagorean_triplets02(n):
 4     triplets = []
 5     n = n + 1
 6     for a in range(0, n):
 7         # for b in range(a, n):  # 此处考虑去重
 8         for b in range(0, n):  # 不去重使用此处
 9             c = n-1 - a - b
10             if a ** 2 + b ** 2 == c ** 2:
11                 triplets.append((a, b, c))
12     return triplets
13 
14 # 记录开始时间
15 start_time = time.time()
16 triplets = find_pythagorean_triplets02(1000)
17 # 记录结束时间
18 end_time = time.time()
19 # 计算执行时间
20 execution_time = end_time - start_time
21 # 打印执行时间
22 print(f"find_pythagorean_triplets01方法执行时间: {execution_time} 秒")
23 print(f"find_pythagorean_triplets01方法执行结果:{triplets}")

输出:

find_pythagorean_triplets01方法执行时间: 0.16266536712646484 秒
find_pythagorean_triplets01方法执行结果:[(0, 500, 500), (200, 375, 425), (375, 200, 425), (500, 0, 500)]

  

去重时限制了b的取值范围,避免了不必要的迭代。避免一次循环(相对不伤脑)

从输出结果上看看,优化后耗时很nice(1000倍)

 

方法3:数学优化(去重,不包括0)

 1 import time
 2 
 3 # 方法3:数学推理优化
 4 def find_pythagorean_triplets03():
 5     triplets = []
 6     for a in range(1, 1000):
 7         b = (500000 - 1000 * a) / (1000 - a)
 8         if b.is_integer() and b > 0:
 9             c = 1000 - a - int(b)
10             triplets.append((a, int(b), c))
11     return triplets
12 
13 
14 
15 
16 # 记录开始时间
17 start_time = time.time()
18 triplets = find_pythagorean_triplets03()
19 # 记录结束时间
20 end_time = time.time()
21 # 计算执行时间
22 execution_time = end_time - start_time
23 # 打印执行时间
24 print(f"find_pythagorean_triplets01方法执行时间: {execution_time} 秒")
25 print(f"find_pythagorean_triplets01方法执行结果:{triplets}")

输出:

find_pythagorean_triplets01方法执行时间: 0.0 秒
find_pythagorean_triplets01方法执行结果:[(200, 375, 425), (375, 200, 425)]

这速度也没谁了。

虽然方法1到方法3没有增加数据量,但优化的结果,在时间执行上,节约很多成本。

 

标签:优劣,复杂度,算法,时间,pythagorean,time,find
From: https://www.cnblogs.com/allenxx/p/17675493.html

相关文章

  • 代码随想录算法训练营第十四天|二叉树的递归法、迭代法
    二叉树的递归遍历(前中后序遍历-递归法与迭代法)递归三部曲:确定递归函数的参数和返回值确定终止条件确定单层递归的逻辑递归法对二叉树进行前中后序遍历(力扣144.145.94.)//前序遍历·递归·LC144_二叉树的前序遍历classSolution{publicList<Integer>preorderTra......
  • Java实现常见排序算法
    Java实现常见排序算法排序也称排序算法(SortAlgorithm),排序是将一组数据,依指定的顺序进行排列的过程。排序的分类:内部排序:指将需要处理的所有数据都加载到内部存储器中进行排序。外部排序法:数据量过大,无法全部加载到内存中,需要借助外部存储进行排序。常见的排序算法分......
  • 找质数(图算法)、交错字符串(字符串、动态规划)、有效数字(字符串)
    找质数(图算法)找出大于200的最小的质数解答:importjava.util.*;importjava.lang.*;importjava.io.*;classIdeone{publicstaticvoidmain(String[]args)throwsjava.lang.Exception{intn=201;while(true){booleanb=tru......
  • 梯度上升算法
    用梯度上升算法进行Logistic回归$w=w+\nabla{f(w)}$对应代码如下importmatplotlib.pyplotaspltimportnumpyasnpfromsklearn.datasetsimportmake_classificationdata_1,labels=make_classification(n_samples=400,n_features=2,n_informative=2,n_redundant=0,n_......
  • 随机森林算法如何用代码实现
    随机森林是一种集成学习算法,通过组合多个决策树来进行分类和回归任务,从而提高预测的稳定性和准确性。以下是使用Python中的sklearn库实现随机森林算法的基本示例:fromsklearn.datasetsimportload_irisfromsklearn.model_selectionimporttrain_test_splitfromsklearn.ensemb......
  • 深度神经网络中基于卷积操作的自适应学习算法研究
    本文提出了一种基于卷积操作的自适应学习算法,用于深度神经网络中。该算法通过引入复杂的数学公式和高阶张量操作,实现了对复杂模式的准确建模和学习。我们通过对网络架构的改进和参数的优化,提高了模型的泛化能力和性能表现。实验结果表明,我们的算法在多个基准数据集上取得了优于现有......
  • 遗传算法
     遗传算法(GeneticAlgorithm)是一种基于自然选择原理和自然遗传机制的启发式搜索算法。该算法通过模拟自然界中生物遗传进化的自然机制(选择、交叉和变异操作),将好的遗传基因(最优目标)不断遗传给子代,使得后代产生最优解的概率增加示例代码如下:#导入所需的库importrandomimportmat......
  • 9.5-铲机什么时候加-限位柱的算法
      ......
  • 【Leetcode刷题记录】各种排序算法
    前言:这篇文章总结一下学习的几种排序算法,假设要对一个vector<int>数组进行降序排序,数组中一共有n个数。1、冒泡排序思想:冒泡排序的思想就是一共进行n-1次循环,每次循环把范围内最小的数冒到最后面。因此用内为双循环,外循环为冒泡的次数,内循环为每次冒泡的范围,通过比较和......
  • C++ 算法竞赛、01 周赛篇 | AcWing 第1场周赛
    AcWing第1场周赛竞赛-AcWing3577选择数字3577.选择数字-AcWing题库朴素暴力两层循环#include<cstdio>#include<iostream>#include<unordered_set>usingnamespacestd;constintN=101;inta[N],b[N];intmain(){intn,m;cin>>n;......