t****d
发帖数: 89 | 1 一个double类型的array名为list，长度为n，设两个点i和j，0
i],list[i+1]到list[j],list[j+1]到list[n]分别算一个score。需要找到i,j两个点，
使得三段的score之和最小。请问有什么好的算法，使得time complexity最小？ |
l*********8
发帖数: 4642 | 2 list[0]到list[i]的score怎么定义？
list[
【在 t****d 的大作中提到】
: 一个double类型的array名为list，长度为n，设两个点i和j，0: i],list[i+1]到list[j],list[j+1]到list[n]分别算一个score。需要找到i,j两个点，
: 使得三段的score之和最小。请问有什么好的算法，使得time complexity最小？
|
l****h
发帖数: 1189 | 3 同问。 这个没定义，就不成个题。
【在 l*********8 的大作中提到】
: list[0]到list[i]的score怎么定义？
:
: list[
|
t****d
发帖数: 89 | 4
score总和 = （i+1）*（list[0]到list[i]数值的variance）+（j-i）*（list[i+1]到
list[j]数值的variance）+（n-j）*（list[j+1]到list[n]数值的variance）
【在 l*********8 的大作中提到】
: list[0]到list[i]的score怎么定义？
:
: list[
|
l*********8
发帖数: 4642 | 5 list[0]到list[i]数值的variance： 是 sum ( (list[k] - mean_value)^2 ), 0<=k
<=i 吗？
【在 t****d 的大作中提到】
:
: score总和 = （i+1）*（list[0]到list[i]数值的variance）+（j-i）*（list[i+1]到
: list[j]数值的variance）+（n-j）*（list[j+1]到list[n]数值的variance）
|
t****d
发帖数: 89 | 6
=k<=i 吗？
list[0]到list[i]数值的variance： 是 sum ( (list[k] - mean_value)^2 )/(i+1),
0<=k<=i
【在 l*********8 的大作中提到】
: list[0]到list[i]数值的variance： 是 sum ( (list[k] - mean_value)^2 ), 0<=k
: <=i 吗？
|
l*n
发帖数: 529 | 7 这么一来score就是方差啊。
用数组记录0到当前的均值和尾到当前的均值，然后n、m配对，可以到O(n^2)吧，毕竟n
和m的可选组合是没办法少于O(n^2)的。
),
【在 t****d 的大作中提到】
:
: =k<=i 吗？
: list[0]到list[i]数值的variance： 是 sum ( (list[k] - mean_value)^2 )/(i+1),
: 0<=k<=i
|
t****d
发帖数: 89 | 8 这样就相当于是exhaustive search, 我在想是不是还有更好的算法呢？
竟n
【在 l*n 的大作中提到】
: 这么一来score就是方差啊。
: 用数组记录0到当前的均值和尾到当前的均值，然后n、m配对，可以到O(n^2)吧，毕竟n
: 和m的可选组合是没办法少于O(n^2)的。
:
: ),
|
l*n
发帖数: 529 | 9 显然O(n)做不到，感觉跟O(nlogn)也没啥关系，还是老老实实O(n^2)吧
【在 t****d 的大作中提到】
: 这样就相当于是exhaustive search, 我在想是不是还有更好的算法呢？
:
: 竟n
|
