明确n是谁
老师您好，这个明确n是谁我有点疑惑，O（n）这里面的n不是广义上的n嘛，然后题目中的n*n和a*a这两个数组指的不是一个变量名嘛，我感觉左边的n*n数组中的n和它的时间复杂度O（n方）中的n不是同一个n阿。以及右边的a*a=n中的n和它的时间复杂度O（n）也不是一个n呀。
思考：比如平时具体代码的时候，遍历一个k*k的数组，问它的时间复杂度，那我加不加k*k=t这个条件，时间复杂度应该也是O（n方）
正在回答
正是因为他们不是一个 n，所以才需要明确 n 是谁呀：）
明确 n 是谁的一大好处就是，你解释的清楚。n 具体到程序里，到底是谁。如果你说“n是广义的”。什么叫广义？你怎么定义广义？
举个例子，比如让你设计一个算法，计算一个数字的所有位的数字和。比如 123 的结果是 1 + 2 + 3 = 6；888888 的结果是 8 + 8 + 8 + 8 + 8 + 8 = 48。这个算法时间复杂度是多少？如果 n 是这个数字的话，这个时间复杂度就是 O(logn)；如果 n 是这个数字代表的字符串长度的话，这个算法的时间复杂度就是 O(n)。那么用你的“广义”的观点来看，取谁？
再举个栗子，课程后面，你会学到实用优先队列来解决 topk 问题，届时，我们会分析出，这个算法的时间复杂度是 O(nlogk) 的。n 和 k 具体表示什么，在问题中有严格的定义。那么用你的“广义”的观点来看，就是 O(nlogn) 吗？不是的，在这个问题中，O(nlogn) 和 O(nlogk) 是不同的。
这样的例子非常多，比如，图论中的 dijkstra 算法，用普通优先队列，复杂度是 O(ElogE) 的，用索引堆，普杂度是 O(ElogV) 的。V 代表图中的顶点数量，E 代表图中的边数。那么用“广义”的观点来看，他们都是 nlogn? n 是谁？而实际上，这两个复杂度是不一样的。
继续加油！：）
-
慕哥8458337 #1
n取不同的值就会有不同的复杂度，所以才需要明确n才能确定复杂度，那明确n是根据什么条件来明确的呀，
比如这个例子这里针对不同n的 明确 ，复杂度还不一样，是可以任意选其一吗。
2021-06-02 15:38:01 -
对的呀。这就像我月薪用人民币算是 1 万元；用美元算是 1600 元。按哪个算？都可以呀！但我需要先定义好，我们聊得是人民币还是美元呀：）
2021-06-02 15:48:39
题主的问题非常好，我在某个瞬间可能也产生这样的疑惑，同样的问题，同样的算法为什么时间复杂度不一样（例如，二维数组的分别是O(n2)和O(n)）。刘老师的例子“计算一个数字的所有位的数字和”，从不同的角度看n，产生了不同的时间复杂度。这个案例，解决了我的疑惑。算法的步骤可能没有变，但是看待n的角度变了，复杂度也变了。n从数值的大小角度看，复杂度为O(logn)级别；n从数值的尾数来看，复杂度为O(n)级别。不可以将O(logn)和O(n)进行比较，因为n的语义是不同的。可以使用任何一种n的语义，但是必须先确定下来，然后将不同算法的时间复杂度惊醒比较。
现在，来看本问题。O(n2)中两个n的语义为二维数组两个维度分别的长度，而O(n)中n的语义为二维数组两个维度的积，你不能拿O(n2)和O(n)进行比较，因为二者中的n意思不一样。其实两者的算法可能完全相同，根本不存在优劣。
恭喜解决一个难题，获得1积分~
来为老师/同学的回答评分吧
0 星