例如，如果合并排序的时间复杂度是 O(n log n) 那么为什么它是大 O 而不是 theta 或 omega。我知道这些的定义，但我不明白的是如何根据定义确定符号。
最佳答案
对于大多数算法，您基本上关心的是其运行时间的上限。例如，您有一些算法可以对数字数组进行排序。现在您很可能会担心算法在最坏情况下的运行速度。
因此，归并排序的复杂性主要写为 O(nlogn)，即使将其表示为 theta(nlogn) 会更好，因为 theta 表示法是更紧的约束。合并排序在 theta(nlogn) 时间内运行，因为无论输入是什么，它总是会消耗这么多时间。
你不会再找到 omega 符号，主要是因为我们关心的是运行时间的上限而不是下限。
关于algorithm - 算法时间复杂度中如何判断是放big O,theta还是omega记法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24226600/