我最近制作了一个自行车行程分析器，您可以在其中输入您的行驶距离和该行程的平均速度，并计算您的时间，将当前速度与您迄今为止输入的所有速度的最小速度，最大速度和平均速度进行比较，然后按照速度，距离和时间来绘制进度（最近10个行程）。一切都按计划进行，除了我必须删除记录（当时是不正确的记录），然后按正常方式运行程序（由于数据库处理索引的原因，编号全部搞砸了）。我添加了一个功能来缓解某些问题，但是并不能完全解决问题。 （由于指定的时间间隔内缺少一些记录号，因此它不会精确显示10条记录。）现在，我正在对其进行改进，并找到了两种方法来实现。
我找到了一种简单的递归方法，以及相应的迭代方法。
递归方式：
private int calculateOffset(int min, int max)
{
int actualTripNumber = 0, expectedTripNumber = 0, totalOffset = 0;
try
{
resultSet = statement.executeQuery("SELECT TripNumber FROM BikeTripRecords WHERE TripNumber > " +
((max == 0) ? String.format("(SELECT max(TripNumber) FROM BikeTripRecords) - %d", maxShowableRecords) :
String.format("%d AND TripNumber < %d", min, max))
);
//we could set expectedTripNumber = min + 1 (and then offset = min + 1), but that would cost one instruction
while (resultSet.next())
{
actualTripNumber = resultSet.getInt(1); //get the actualTripNumber
totalOffset += ((expectedTripNumber > 0) ? actualTripNumber - expectedTripNumber : actualTripNumber - (min + 1)); //calculate the offset
expectedTripNumber = actualTripNumber + 1; //we expect the next actualTripNumber to be one more than the current one
}
}
catch (SQLException exception)
{
exception.printStackTrace();
return -1; //You KNOW something went wrong with a negative return value; this could be replaced by System.exit(1), however
}
//conditional tail recursion; this should end with the last recursive call to return 0
if (totalOffset > 0)
{
//if this function was called from the outside
if (max == 0)
{
//we assign to max the first number from the resultSet
int newMax = resultSet.getInt(1);
totalOffset += calculateOffset(newMax - totalOffset, newMax);
}
else
{
totalOffset += calculateOffset(min - totalOffset, min);
}
}
return totalOffset;
}
迭代方式：
private int calculateOffset()
{
//This version of calculateOffset() will be ITERATIVE, not recursive (and will use a helper function)
int totalOffset = 0, intervalOffset = 1000; //giving intervalOffset a garbage value (so that we could use it in the while loop)
int minimum = 0, maximum = 0;
//this is the first calculation; we obtain the max(TripNumber) from BikeTripRecords (this method will only be called ONCE)
try
{
resultSet = statement.executeQuery("SELECT max(TripNumber) FROM BikeTripRecords");
resultSet.next();
maximum = resultSet.getInt(1); //fetching maximum
minimum = maximum - maxShowableRecords; //while we are at it, we might as well assign minimum a value here, too...
}
catch (SQLException exception)
{
exception.printStackTrace();
return -1; // You know something went wrong when the return value is negative!!
}
//we simply add to totalOffset the return value of our helper function (the offset of the intervals specified) while it doesn't return 0
while (intervalOffset > 0)
{
intervalOffset = getIntervalOffset(minimum, maximum); //get the intervalOffset
totalOffset += intervalOffset; //add it to the totalOffset
//recalculate maximum, minimum
maximum = minimum;
minimum -= intervalOffset;
}
return totalOffset;
}
//helper function
private int getIntervalOffset (int min, int max)
{
int offset = 0; //the value of this variable will be the return value (if everything goes according to plan)
int actualTripNumber = 0, expectedTripNumber = 0;
try
{
resultSet = statement.executeQuery(String.format("SELECT TripNumber FROM BikeTripRecords WHERE TripNumber > %d AND TripNumber <= %d", min, max));
//computing the offset of the interval
while (resultSet.next())
{
actualTripNumber = resultSet.getInt(1); //getting the actualTripNumber
//the only offset there should be the first time around should be the difference between the actualTripNumber and one more than the min
//otherwise, the offset should be the difference between the actualTripNumber and the expectedTripNumber
offset += ((expectedTripNumber > 0) ? actualTripNumber - expectedTripNumber : actualTripNumber - (min + 1));
expectedTripNumber = actualTripNumber + 1; //the expectedTripNumber should be one more than the actualTripNumber
}
}
catch (SQLException exception)
{
exception.printStackTrace();
return -1; // How you KNOW something went wrong....
}
return offset;
}
两个代码段均检查k个间隔（k为正整数）。我很困惑的是每种方法的算法复杂度的计算。两种方法的关键部分完全相同：一个while循环执行正好10-m次（m是所检查间隔中丢失记录的计算数量）。在这里，我们可以肯定地说m在10的上方。我为这两种方法得出的复杂度相对于k和sum（mj，j在1与k之间）是线性的，即32k-（2+递归方式为3和（mj，j在1和k-1之间），递归方式为4 + 31k-3和（mj，j在1和k-1之间）。 （在这里，mj读取“ m sub j”。）两种算法的复杂性是否将被摊销或为O（max {k，sum（mj，j在1和k-1之间）}）？
最佳答案
为什么不为自己省去头痛，而仅获得最近的10个结果？
由于使用的是derby，因此可以使用以下方法限制结果：
statement.setMaxRows(10);
然后，假设您的
TripNumber列是一个自动递增的ID，您可以对结果进行排序：SELECT TripNumber FROM BikeTripRecords
ORDER BY TripNumber DESC