F*****o
发帖数: 32 | 1 x_0 = C (integer)
if x_n is even then x_{n+1} is x_n / 2
if x_n is odd then x_{n+1} to be 3 * x_n + 1
这题的复杂度是O(logC)吗？ |
E******t
发帖数: 28 | 2 Typed a long response which got lost, pretty pissed...
Ok so I am learning too and would like to hear what others think about it.
I think it depends on the algorithm one chooses to use.
- hash table: complexity is O(n): every intermediate step result X_i gets
stored in a hashtable indexed by i. and every step takes time O(1), X_n
takes O(n);
- brute force calculation takes exponential time, like Fibonacci number.
every step X_i needs to go back to X_i-1...so it becomes O(n^n)?
Is this right? |
l*3
发帖数: 2279 | 3 问的什么意思？
停止的时候的迭代步数？
停止是指某个x_k=1？ |
l********l
发帖数: 91 | 4 最后收敛于1,4,2,1,4,2... 复杂度我觉得是O(1) |
k********n
发帖数: 99 | 5 这个1,4,2,1,4,2... 怎么算出来的 我随便举了几个例子似乎是发散的啊。
【在 l********l 的大作中提到】
: 最后收敛于1,4,2,1,4,2... 复杂度我觉得是O(1)
|
l********l
发帖数: 91 | 6 请指教。个人理解说的是这个：
https://zh.wikipedia.org/zh-cn/%E8%80%83%E6%8B%89%E5%85%B9%E7%8C%9C%E6%83%B3
【在 k********n 的大作中提到】
: 这个1,4,2,1,4,2... 怎么算出来的 我随便举了几个例子似乎是发散的啊。
|
b***e
发帖数: 1419 | 7 这个序列的收敛性是著名的数论难题。费马定理整出来了这个还悬着呢。
【在 F*****o 的大作中提到】
: x_0 = C (integer)
: if x_n is even then x_{n+1} is x_n / 2
: if x_n is odd then x_{n+1} to be 3 * x_n + 1
: 这题的复杂度是O(logC)吗？
|
t***t
发帖数: 6066 | |
A***o
发帖数: 358 | 9 Isn't it an inf loop?
【在 F*****o 的大作中提到】
: x_0 = C (integer)
: if x_n is even then x_{n+1} is x_n / 2
: if x_n is odd then x_{n+1} to be 3 * x_n + 1
: 这题的复杂度是O(logC)吗？
|
x*******9
发帖数: 138 | 10 没follow up一道 P = NP的证明么。。。 |
|
|
I****0
发帖数: 182 | 11 对于这种循环问题，hash table应该是标准解法吧？
【在 E******t 的大作中提到】
: Typed a long response which got lost, pretty pissed...
: Ok so I am learning too and would like to hear what others think about it.
: I think it depends on the algorithm one chooses to use.
: - hash table: complexity is O(n): every intermediate step result X_i gets
: stored in a hashtable indexed by i. and every step takes time O(1), X_n
: takes O(n);
: - brute force calculation takes exponential time, like Fibonacci number.
: every step X_i needs to go back to X_i-1...so it becomes O(n^n)?
: Is this right?
|
h**p
发帖数: 211 | |
g******d
发帖数: 152 | 13 O(N) 吧
知道x0 求 x1，2，3，4 一直到N |
j**w
发帖数: 382 | |
c*******e
发帖数: 373 | 15 平均复杂度是o(n)
因为计算过程，必定不会出现曾经过的数字
所有的整数，按计算成1所需的迭代次数排序，得到一个新的序列
新序列的序号的总和，和数值本身（也就是原自然数序列的序号）的总和是相等的
所以从中随机选一个数开始计算，最终变成4、2、1，次数可能比n大，也可能比n小，
但是总平均值，就是n |
c*******e
发帖数: 373 | 16 继续算，就会发现不发散了
数字里，奇数因子越多，一上来数值本身会扩大，似乎是发散的
但是数值变大的过程中，其中的奇数因子会逐渐变少，偶数因子变多，然后就开始收敛了
【在 k********n 的大作中提到】
: 这个1,4,2,1,4,2... 怎么算出来的 我随便举了几个例子似乎是发散的啊。
|
s**r
发帖数: 1660 | 17 re
【在 c*******e 的大作中提到】
: 平均复杂度是o(n)
: 因为计算过程，必定不会出现曾经过的数字
: 所有的整数，按计算成1所需的迭代次数排序，得到一个新的序列
: 新序列的序号的总和，和数值本身（也就是原自然数序列的序号）的总和是相等的
: 所以从中随机选一个数开始计算，最终变成4、2、1，次数可能比n大，也可能比n小，
: 但是总平均值，就是n
|
