小弟是个新手,只会写简单的代码实现结果,对于语法的复杂度没有太多概念,使用以下链接完成领扣第 167 题时,提交代码验证到最后一步 16/17,提示:超出时间限制,感觉可能是遍历列表太多次了,但是如何知道每一步的时间复杂度到底有多大呢?
1
Raisu 2018-09-21 15:54:01 +08:00
l , r = 0, len(numbers) -1
while numbers[l] + numbers[r] != target: if numbers[l] + numbers[r] > target: r -= 1; else: l += 1 return [l+1, r+1] |
2
youngitachi 2018-09-21 16:08:16 +08:00
原本最简单(但是不完全靠谱)的方法就是看有几层 for 循环,但是你调用库函数却遮盖了你对复杂度的分析。
想想看 index 函数的复杂度哈,虽然没去看源码,但是这个查找应该还是去顺序遍历的,也就是说,相当于还是要用一个 for 循环去遍历的,故实际上是两层 for 循环的复杂度,O(N^2)咯。 这题有 O(N)的解法,次一点,你在查找的时候写个二分查找,也可以到 O(N log(N)),一楼的写法就是 O(N)的,可以好好体会一下(先自己想想解法吧)。 |
3
d18 2018-09-21 16:15:47 +08:00
同学,刷题就不要用 python 了,和作弊有什么区别。
像这句“ if sec_num in numbers:”,就是遍历了一遍列表,不超时就怪了。 |
4
LadyChunsKite 2018-09-21 16:28:28 +08:00
@d18 刷题用 python 怎么就作弊了?算法题和语言有什么关系?
|
5
menc 2018-09-21 16:42:10 +08:00
@LadyChunsKite
有关系,不好算时间复杂度。 if element in list: blabla 这句话看起来像一句话,实际上是 O(n)的时间复杂度。 python 内置 sort 好用的一比,还内置了 itertools 这些东西,实现全排列和笛卡尔积都是一句话的事。 可是你知道它们时间复杂度是多少么? 如果题目考察的就是全排列的实现,你用 itertools 又有什么意义。 所以如果一定要用 python,建议写成 C 那样原始的形式,但是这样一定有人说“不优雅 /不 pythonic/python 内置了干嘛不用”。 那就别用 python 了,统一用 c/cpp 吧。 |
8
menc 2018-09-21 17:04:06 +08:00
|
9
liprais 2018-09-21 17:11:54 +08:00
https://www.v2ex.com/t/382458#reply59
v2ex 有一点好处就是不能删帖 |
10
stevenbipt 2018-09-21 17:15:43 +08:00 via Android
Python 太慢了,更得考虑时间复杂度问题了,C/C++和 java 速度相对快上不少,n²复杂度应该都不会出线超时,但是 Python 不好说
|
11
LadyChunsKite 2018-09-21 17:17:21 +08:00
@menc 我觉得这不是 python 的问题,而是写代码的人的问题。一些 easy 题确实用一些 pythonic 的代码很轻松就解决了。但是我觉得,随着问题难度的上升,不是靠几个 sort,几个 in 就能解决的。
就拿这题来说: https://leetcode.com/problems/boats-to-save-people/description/ 要用到排序,但我觉得没必要把排序算法写一遍,考察的重点不是排序。 |
12
lance6716 2018-09-21 17:17:34 +08:00 via Android
@liprais 北航挺好啊,我们小破邮瑟瑟发抖
另外 Cpython 像我这种非 CS 专业的都能看懂,其实并不算很刁钻的要求… |
13
sagaxu 2018-09-21 17:21:22 +08:00 via Android
@menc sort 在 python 中的复杂度,跟 cpp 的或者 java 的不应该有数量级上的差异。除非自己手动 sort,否则任何语言的 sort 库都会面临 python 一样的问题。
排列组合库,时间复杂度可以认为是结果条数乘以每条长度。主流实现都应该大差不差。 |
14
ylsc633 2018-09-21 17:23:27 +08:00
没用 python 解过
很多题目限制 时间和空间复杂度, 偶尔还要原地! 你们用内置函数的 怎么计算这些啊? |
19
loryyang 2018-09-21 19:17:27 +08:00
不是,这题就是故意卡你这种解法的,你这种暴力的方法肯定会被 judge 卡成 TLE 的。。
至于分析时间复杂度,这个你去学学呗,不难的 |
20
Raisu 2018-09-21 19:34:32 +08:00
dic = {}
for i in range(len(numbers)): if numbers[i] in dic: if target - numbers[i] == numbers[i]: return [dic[numbers[i]].pop(), i + 1] else: dic[numbers[i]] = [i + 1] for k in dic: if target - k in dic: if dic[k][0] < dic[target - k][0]: return [dic[k][0], dic[target - k][0]] else: return [dic[target - k][0], dic[k][0]] 讨论组里面用字典的解法,可以通过,原因是字典的检索速度会比较快一点。。。 |
21
Raisu 2018-09-21 19:36:15 +08:00
我也是新手啊。。。自学转开发才半年,
|
22
Raisu 2018-09-21 19:54:01 +08:00
试了一下,用 set 过滤了一下也能通过。。。。不过有点取巧就是了。代码怎么带格式?
l = len(numbers) a = target // 2 if a in numbers: index = numbers.index(a) if a in numbers[index + 1:]: return [index+1, index + 2] n = list(set(numbers)) for i in range(len(n)): ans = target - n[i] if ans in n: index2 = numbers.index(ans) index1 = numbers.index(n[i]) return sorted([index1 + 1, index2 + 1]) |
25
vancoder 2018-09-22 02:14:11 +08:00
这不是 python 效率的问题,是你的解法时间复杂度的问题,建议学习一下如何分析算法时间复杂度
|
26
widewing 2018-09-22 08:39:32 +08:00 via Android
没搞错吧楼上的各位,哪个语言没有个内置的 sort?莫非你们都用汇编的?
|
27
cyrbuzz 2018-09-22 11:22:32 +08:00 1
代码里有 print,把 print 去掉吧...
in 这种语句尽量用 set 代替 list 吧。list 执行是 O(n) ,set 是 O (1)。 这个题应该是想让你用 O(n) 的解法来解,否则不会又出来一个标明 已排过序 的在用 未排过序 时的解法再解一次吧... |