chapter_computational_complexity/summary/

[giscus[bot]]

chapter_computational_complexity/summary/

Your first book to learn Data Structure And Algorithm.

https://www.hello-algo.com/chapter_computational_complexity/summary/

[hatkd]

作者你好，我发现本书中c语言的部分并没有给出实现，对于部分大一的学生不大友好，如果可以，我希望贡献我关于对于那一部分，并在别的平台发布不知道是否可以

[krahets]

哈喽，欢迎贡献 C 代码！详情请见 #15
如果是个人非商业转载，请注明作者 Krahets 和出处链接；不接受商业转载。

[hatkd]

好的好的

[derekzhan]

文章中为什么要用( 格式呢，看着好别扭 😁

[krahets]

Hi 你是指「」括号吗？

[zhuasdfg]

Q&A有点看不懂，回来再看

[FantasyLeo]

Q&A 中关于 “函数和方法这两个术语的区别是什么？”的回答很具有参考意义，有启发。但是“因此”后面的表述就不够恰当，有点误导。

[krahets]

谢谢指出！已更新

[nonhana]

争取每天浏览一整章~

[Hu-Said]

Q & A中关于自动优化尾递归的编程语言补充一下，在C# 7.0及以上版本，编译器已经开始支持尾递归的优化，称为"尾调用"。当编译器检测到一个函数调用是尾递归时，它会自动将尾递归优化为迭代形式，避免创建新的栈帧和堆栈溢出。但需要注意的是，这个优化只会在Release模式下生效，而在Debug模式下，编译器不会进行尾调用优化。

[coderguai]

每天学一点点😁

[AceLi12138]

赞赞赞

[giftfm]

都说要学习c++的特性，不过要怎么学习，怎么才算学会c++的特性？

[fantiyun]

赞，请大家继续加油！

[Mrzhang007]

已学习 打卡

[WheatJack]

打卡

[2nite2]

打卡

[bclnb666]

加油

[WalkerInAI]

我对函数渐进上界的定义有些困惑，到底是O(n)是函数渐进上界，还是O( f(n) )是函数渐进上界呀？

[krahets]

都是呀，你举的两个例子 f(n) = n ，计算时间复杂度其实就是找这个 f(n)

[WalkerInAI]

在我看来算法效率评估中的复杂度分析与实际测试有点像加速度与速度的关系。就像看一辆车的速度性能，是看它跑一百米需要多长时间，还是看它加速到100km/h需要多长时间。
这也很像公司招人，是该看他目前的成绩，还是该看他进公司后能为公司创造的成绩。
前者是静态的，后者是动态的。

[javamyth]

这里应该得加上Go,Go 也是支持过程式编程(函数),也支持面向对象编程(方法)。 未来Go 的市场 占有也不小哦。

---

下面以几种常见的编程语言为例来说明。

C 语言是过程式编程语言，没有面向对象的概念，所以只有函数。但我们可以通过创建结构体（struct）来模拟面向对象编程，与结构体相关联的函数就相当于其他编程语言中的方法。
Java 和 C# 是面向对象的编程语言，代码块（方法）通常作为某个类的一部分。静态方法的行为类似于函数，因为它被绑定在类上，不能访问特定的实例变量。
C++ 和 Python 既支持过程式编程（函数），也支持面向对象编程（方法）。

[javamyth]

这里建议增加支持尾递归的编程语言说明。如Lisp系列语言，函数式编程语言，GCC编译器的C语言等

---

理论上，尾递归函数的空间复杂度可以优化至
。不过绝大多数编程语言（例如 Java、Python、C++、Go、C# 等）不支持自动优化尾递归，因此通常认为空间复杂度是
。

[HuaWang135608]

Over

[NgxuAnGMH]

真的特别赞 👍 太棒了这个教程

[NgxuAnGMH]

Q & A 中：函数 和 方法 两个术语的区别，初学者可以认真记一下？后续如果看书遇到这么一句话“函数是一等公民”，就可以反应过来了。在现代编程语言的设计中，得益于后端编译技术的发展，很多语言都配置了这种特性，可以简单理解为：必要时候，可以将函数作为一个参数进行传递。

[NgxuAnGMH]

如果不考虑运行时（编译器后端）的差异，其实任何一门语言的语法（编译器前端），都是特别相似的。语言之间最大的不同，还是编译技术上的创新设计。以后端为例，从 C 到 C++ 到 Java，erlang 到 go 到 Rust，每一种语言的诞生都有自己想要集中 focus 解决的问题。

[xiaoyaozizaiwoweidu]

函数是一等公民，可以赋值，可以作为参数传递，可以作为返回值

[HP-Patience]

2024.5.26打卡😊
易忘：
1.尾递归在递的操作中就已经完成数据的运算，在归的时候向上返回同样的数，所以说可以优化，但是大多数语言不支持尾递归优化，所以大多数语言的尾递归空间复杂度仍为O(n)，而不是O(1)
2.理解栈帧空间的概念，想像成子弹弹夹，递归调用函数时把函数当作子弹放入，在归的时候后进的函数先出。
3.还记得时间/空间复杂度常见类型有哪些吗？每个类型对应的例子还记得吗？

[HP-Patience]

4.循环中的变量和函数所占空间复杂度为O(1)，记得为什么吗？

[DeBut258]

复杂度分析是评估算法效率的重要工具。在算法设计和实现过程中，时间复杂度和空间复杂度是衡量算法优劣的两个主要指标。时间复杂度用于衡量算法运行时间随输入数据规模增长的变化趋势，而空间复杂度则关注算法占用的内存空间随输入数据量增长的变化。

在时间复杂度方面主要关注的是算法在最差情况下的表现，

复杂度分析还包括平均时间复杂度和最优时间复杂度。平均时间复杂度反映算法在随机数据输入下的运行效率，最接近实际应用中的表现。最优时间复杂度则几乎不用，因为输入数据一般需要满足严格条件才能达到最佳情况。

[DeBut258]

时间复杂度O(1): 常数时间复杂度。无论输入数据规模多大，算法的执行时间始终不变。比如，访问数组中的某个元素。
def get_first_element(arr):
return arr[0]

[DeBut258]

时间复杂度O(log n): 对数时间复杂度。算法的执行时间随着输入数据规模的增加呈对数增长。比如，二分查找算法。
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

[DeBut258]

O(n): 线性时间复杂度。算法的执行时间随着输入数据规模的增加线性增长。比如，遍历一个列表。
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1

[DeBut258]

O(n log n): 线性对数时间复杂度。常见于一些高效的排序算法，比如快速排序和归并排序。
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)

def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result

[DeBut258]

O(n^2): 平方时间复杂度。常见于一些简单的排序算法，比如冒泡排序和选择排序。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr

[Cy-boy5]

day02-复杂度分析

2024-6-22