时间戳

首页 > 解决方案 > 大 O（常数）时间复杂度

algorithm - 大 O（常数）时间复杂度

问题描述

为什么每个语句的以下代码都引用大 O 常量（这里我使用 1 作为约定）？

我的意思是，如果数组大小变大，时间复杂度可能会变大，对吗？而且总数会越来越大，不会影响复杂度吗？

伪代码：

def find_sum(given_array)
    total = 0 # refers to O(1)
    for each i in given array: #O(1) 
      total+=i #O(1)
    return total #O(1)

标签： algorithmtime-complexitybig-ocomplexity-theory

解决方案

TL;DR：因为大 O 表示法用于量化算法，关于它如何随着输入的增加而表现。

我的意思是，如果数组大小变大，时间复杂度可能会变大，对吗？而且总数会越来越大，不会影响复杂度吗？

您将算法所花费的时间误认为是时间复杂度。

让我们首先澄清Big O当前上下文中的符号是什么。从（来源）可以阅读：

大 O 表示法是一种数学表示法，用于描述当参数趋于特定值或无穷大时函数的限制行为。(..)在计算机科学中，大 O 表示法用于根据算法的运行时间或空间需求如何随着输入大小的增长而增长来对算法进行分类。

非正式地，在计算机科学的时间复杂性和空间复杂性理论中，人们可以将Big O符号视为算法的一种分类，它们分别具有关于时间和空间的某种最坏情况。例如，O(n)：

如果算法的时间/空间复杂度为 O(n)，则称该算法采用线性时间/空间或 O(n) 时间/空间。非正式地，这意味着运行时间/空间最多随着输入（source）的大小线性增加。

所以对于这段代码：

def find_sum(given_array)
    total = 0
    for each i in given array:
      total+=i 
    return total

复杂性是O(n)因为随着输入的增加，复杂性会线性增长，而不是恒定的。更准确地说Θ(n)。

IMO 找出复杂性不是很准确，例如：

def find_sum(given_array)
    total = 0 # refers to O(1)
    for each i in given array: #O(1) 
      total+=i #O(1)
    return total #O(1)

由于该Big O符号表示一组具有一定渐近上限的函数；正如人们可以从源代码中读取的那样：

大 O 符号根据其增长率来表征函数：具有相同增长率的不同函数可以使用相同的O符号表示。

更准确的是：

def find_sum(given_array)
    total = 0 # takes c1 time 
    for each i in given array: 
      total+=i # takes c2 time 
    return total # takes c3 time

所以时间复杂度是c1 + n * c2 + c3，可以简化为 n。由于这个函数的下界和上界是一样的，我们可以Θ(n)用O(n).

推荐阅读