LeetCode 392超时，但实在不觉得有小于O(n)的方法

freeaccount 发表于 2016-10-23 17:44
其实我要表达的是，leetcode会不会因为C是编译成native executable所以会比其它语言快（虽然未必）导 ...

大不了strlen是个O(n)循环再是个O(n)那O(2n)还是O(n)嘛

如果strlen每次循环都是O(n)，那n次调用strlen的时间复杂度就是O(n^2)，而非O(2n). 另外编译器确实能够可以优化掉，但是不能假设这点总成立，特别在刷题网站上，为了暴露出代码的实际复杂度，很可能会特意关闭优化。

stellari 发表于 2016-10-23 13:59
如果strlen每次循环都是O(n)，那n次调用strlen的时间复杂度就是O(n^2)，而非O(2n). 另外编译器确实能 ...

我的意思是。。。我假设编译器会优化，这样我的for循环在进入时，会计算一次strlen，是O(n)，之后不会再计算，然后循环本身是个O(n)， 这样总的算法还是O(n)，只是常数因子不同。