UC知道关于数据结构的问题规模和算法效率的疑问
来源：百度知道 编辑：UC知道 时间：2024/09/23 12:08:21
我刚学数据结构不久，对两个概念有点不太理解。请各位知道的朋友指教一下：
1）问题规模n：
究竟什么是问题规模。如：对一个长度为n的线性链表，查找它的第i个元素，返回他的data，那么这个问题的问题规模是n还是i？它的时间复杂度是O（1），还是O（i）？明显不是线性阶O（n），因为它跟长度n无关，无论该线性表多长，我查找的都是第i个元素。
2）假设有两个算法：算法1有两个for循环，每个for循环都执行n次i++；算法2只有一个for循环，但是这个for循环执行n次i++和j++。
书上说，时间复杂度是根据最里层循环的基本操作的次数的数量级来决定的。那么对于算法2，他的基本操作是i++还是j++，抑或是i++与j++之和？实际上两算法总共执行的基本操作(i++和j++)的语句频度是一样的，那么他们的算法效率是一样的吗？都是O（n）吗？
1）问题规模n：
究竟什么是问题规模。如：对一个长度为n的线性链表，查找它的第i个元素，返回他的data，那么这个问题的问题规模是n还是i？它的时间复杂度是O（1），还是O（i）？明显不是线性阶O（n），因为它跟长度n无关，无论该线性表多长，我查找的都是第i个元素。
2）假设有两个算法：算法1有两个for循环，每个for循环都执行n次i++；算法2只有一个for循环，但是这个for循环执行n次i++和j++。
书上说，时间复杂度是根据最里层循环的基本操作的次数的数量级来决定的。那么对于算法2，他的基本操作是i++还是j++，抑或是i++与j++之和？实际上两算法总共执行的基本操作(i++和j++)的语句频度是一样的，那么他们的算法效率是一样的吗？都是O（n）吗？
1 都是n，i是随机的，在n的范围里面，当然和n有关～O（N）不是等于n,是n的一个倍数，是一个复杂度表示，不是确切的数。
2 第一个算法，两层FOR，是0(N^2)复杂度；第二个算法，当然两个操作都是基本操作，复杂度是O(N)。你如果还不理解，建议你还是好好吧大O表示法好好看一次。