這是一個O（n）時間和O（sqrt（n））空間算法。 在文章的第二部分，它將擴展到一個線性時間和O（n ^（1/t））空間算法的任意正整數t。高級思想：將列表拆分爲sqrt（n）很多（幾乎）相同大小的部分。 使用天真的線性時間線性空間方法，從最後一個到第一個，以相反的順序依次打印零件。
要存儲零件的起始節點，我們需要一個大小爲O（sqrt（n））的數組。 要恢復大小約爲sqrt（n）的部分，樸素算法需要一個數組來存儲對部件節點的引用。因此，陣列具有尺寸的O（SQRT（N）。
One使用大小k=[sqrt(n)]+1 =O(sqrt(n)) （LSA ...大步驟陣列，SSA ..小步陣列）的兩個陣列（lsa和ssa）
階段1：（如果鏈接的列表的尺寸是未知的找出N，它的長度）： 通過從開始在列表中移動到另一端，計數列表中的元素，這需要ñ步驟
階段2： 將單個鏈表的每個第k個節點存儲在數組lsa中。這需要n個步驟。
階段3： 按相反順序處理lsa列表。打印以相反的順序 每個部分這還需要N個步驟
所以該算法的運行時間爲3n = O（n）和它的速度爲約2 * SQRT（N）= O（SQRT（n））的。
這是一個Python 3。5執行：
import cProfile
import math
class LinkedListNode:
def __init__(self, value, next_node):
self.value = value
self._next_node = next_node
def next_node(self):
return(self._next_node)
def reverse_print(self):
# Phase 1
n=0
node=self
while node:
n+=1
node=node.next_node()
k=int(n**.5)+1
# Phase 2
i=0
node=self
lsa=[node]
while node:
i+=1
if i==k:
lsa.append(node)
i=0
last_node=node
node=node.next_node()
if i>0:
lsa.append(last_node)
# Phase 3
start_node=lsa.pop()
print(start_node.value)
while lsa:
last_printed_node=start_node
start_node=lsa.pop()
node=start_node
ssa=[]
while node!=last_printed_node:
ssa.append(node)
node=node.next_node()
ssa.reverse()
for node in ssa:
print(node.value)
@classmethod
def create_testlist(nodeclass, n):
''' creates a list of n elements with values 1,...,n'''
first_node=nodeclass(n,None)
for i in range(n-1,0,-1):
second_node=first_node
first_node=nodeclass(i,second_node)
return(first_node)
if __name__ == "__main__":
n=1000
cProfile.run('LinkedListNode.create_testlist(n).reverse_print()')
print('estimated number of calls of next_node',3*n)
它輸出下面的輸出（在端部是分析器的輸出中顯示的函數調用數目）：
>>>
RESTART: print_reversed_list3.py
1000
999
998
...
4
3
2
1
101996 function calls in 2.939 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 2.939 2.939 <string>:1(<module>)
2000 0.018 0.000 2.929 0.001 PyShell.py:1335(write)
1 0.003 0.003 2.938 2.938 print_reversed_list3.py:12(reverse_print)
1 0.000 0.000 0.001 0.001 print_reversed_list3.py:49(create_testlist)
1000 0.000 0.000 0.000 0.000 print_reversed_list3.py:5(__init__)
2999 0.000 0.000 0.000 0.000 print_reversed_list3.py:9(next_node)
...
estimated number of calls of next_node 3000
>>>
調用next_node（）的數目是3000如預期
除了使用幼稚O（M）空間算法來打印以相反的順序一個可以使用這種O（SQRT（米））的空間算法長度m的子列表的。但我們必須在子列表的數量和子列表的長度之間找到適當的平衡點：
階段2： 將簡單鏈表拆分爲長度爲n ^（2/3）的n ^（1/3）子列表， 。這些子列表的起始節點存儲在一個長度爲n（1/3）的數組中，使用O（sqrt（m））以相反的順序打印每個長度爲m = n ^（2/3）的子列表））空間算法。因爲m = n ^（2/3），我們需要m ^（1/2）= n ^（1/3）空間。
我們現在有一個爲O（n ^（1/3））需要4N時間等空間算法仍然是O（n）
我們可以分裂成n ^再次重複這個（1/4 ）長度爲m = n ^（3/4）的子列表由O（m ^（1/3））= O（n ^（1/4））空間算法處理，其需要5n = O（n） 。
我們可以一次又一次地重複這一點，併到達一個下面的語句：
大小爲n的不可變的簡單鏈接列表可以以相反的順序使用T * N ^（1/T）= O進行打印（ ñ^（1/t））的空間和（T + 1）N = O（n）的時間，其中t是一個任意正整數
如果不修復t，但從n個這樣的根據選擇噸那麼n ^（1/t））約爲2，即最小的有用數組大小，則這導致由OP描述的O（nlog（n））時間和O（log（n））空間算法。
如果選擇t = 1，則這導致O（n）時間和O（n）空間樸素算法。
這裏是算法的實現
import cProfile
import math
import time
class LinkedListNode:
'''
single linked list node
a node has a value and a successor node
'''
stat_counter=0
stat_curr_space=0
stat_max_space=0
stat_max_array_length=0
stat_algorithm=0
stat_array_length=0
stat_list_length=0
stat_start_time=0
do_print=True
def __init__(self, value, next_node):
self.value = value
self._next_node = next_node
def next_node(self):
self.stat_called_next_node()
return(self._next_node)
def print(self):
if type(self).do_print:
print(self.value)
def print_tail(self):
node=self
while node:
node.print()
node=node.next_node()
def tail_info(self):
list_length=0
node=self
while node:
list_length+=1
last_node=node
node=node.next_node()
return((last_node,list_length))
def retrieve_every_n_th_node(self,step_size,list_length):
''' for a list a of size list_length retrieve a pair there the first component
is an array with the nodes
[a[0],a[k],a[2*k],...,a[r*k],a[list_length-1]]]
and the second component is list_length-1-r*k
and
'''
node=self
arr=[]
s=step_size
index=0
while index<list_length:
if s==step_size:
arr.append(node)
s=1
else:
s+=1
last_node=node
node=node.next_node()
index+=1
if s!=1:
last_s=s-1
arr.append(last_node)
else:
last_s=step_size
return(arr,last_s)
def reverse_print(self,algorithm=0):
(last_node,list_length)=self.tail_info()
assert(type(algorithm)==int)
if algorithm==1:
array_length=list_length
elif algorithm==0:
array_length=2
elif algorithm>1:
array_length=math.ceil(list_length**(1/algorithm))
if array_length<2:
array_length=2
else:
assert(False)
assert(array_length>=2)
last_node.print()
self.stat_init(list_length=list_length,algorithm=algorithm,array_length=array_length)
self._reverse_print(list_length,array_length)
assert(LinkedListNode.stat_curr_space==0)
self.print_statistic()
def _reverse_print(self,list_length,array_length):
'''
this is the core procedure of the algorithm
if the list fits into the array
store it in te array an print the array in reverse order
else
split the list in 'array_length' sublists and store
the startnodes of the sublists in he array
_reverse_print array in reverse order
'''
if list_length==3 and array_length==2: # to avoid infinite loop
array_length=3
step_size=math.ceil(list_length/array_length)
if step_size>1: # list_length>array_length:
(supporting_nodes,last_step_size)=self.retrieve_every_n_th_node(step_size,list_length)
self.stat_created_array(supporting_nodes)
supporting_nodes.reverse()
supporting_nodes[1]._reverse_print(last_step_size+1,array_length)
for node in supporting_nodes[2:]:
node._reverse_print(step_size+1,array_length)
self.stat_removed_array(supporting_nodes)
else:
assert(step_size>0)
(adjacent_nodes,last_step_size)=self.retrieve_every_n_th_node(1,list_length)
self.stat_created_array(adjacent_nodes)
adjacent_nodes.reverse()
for node in adjacent_nodes[1:]:
node.print()
self.stat_removed_array(adjacent_nodes)
# statistics functions
def stat_init(self,list_length,algorithm,array_length):
'''
initializes the counters
and starts the stop watch
'''
type(self)._stat_init(list_length,algorithm,array_length)
@classmethod
def _stat_init(cls,list_length,algorithm,array_length):
cls.stat_curr_space=0
cls.stat_max_space=0
cls.stat_counter=0
cls.stat_max_array_length=0
cls.stat_array_length=array_length
cls.stat_algorithm=algorithm
cls.stat_list_length=list_length
cls.stat_start_time=time.time()
def print_title(self):
'''
prints the legend and the caption for the statistics values
'''
type(self).print_title()
@classmethod
def print_title(cls):
print(' {0:10s} {1:s}'.format('space','maximal number of array space for'))
print(' {0:10s} {1:s}'.format('', 'pointers to the list nodes, that'))
print(' {0:10s} {1:s}'.format('', 'is needed'))
print(' {0:10s} {1:s}'.format('time', 'number of times the method next_node,'))
print(' {0:10s} {1:s}'.format('', 'that retrievs the successor of a node,'))
print(' {0:10s} {1:s}'.format('', 'was called'))
print(' {0:10s} {1:s}'.format('alg', 'algorithm that was selected:'))
print(' {0:10s} {1:s}'.format('', '0: array size is 2'))
print(' {0:10s} {1:s}'.format('', '1: array size is n, naive algorithm'))
print(' {0:10s} {1:s}'.format('', 't>1: array size is n^(1/t)'))
print(' {0:10s} {1:s}'.format('arr', 'dimension of the arrays'))
print(' {0:10s} {1:s}'.format('sz', 'actual maximal dimension of the arrays'))
print(' {0:10s} {1:s}'.format('n', 'list length'))
print(' {0:10s} {1:s}'.format('log', 'the logarithm to base 2 of n'))
print(' {0:10s} {1:s}'.format('n log n', 'n times the logarithm to base 2 of n'))
print(' {0:10s} {1:s}'.format('seconds', 'the runtime of the program in seconds'))
print()
print('{0:>10s} {1:>10s} {2:>4s} {3:>10s} {4:>10s} {5:>10s} {6:>5s} {7:>10s} {8:>10s}'
.format('space','time','alg','arr','sz','n','log', 'n log n','seconds'))
@classmethod
def print_statistic(cls):
'''
stops the stop watch and prints the statistics for the gathered counters
'''
run_time=time.time()-cls.stat_start_time
print('{0:10d} {1:10d} {2:4d} {3:10d} {4:10d} {5:10d} {6:5d} {7:10d} {8:10.2f}'.format(
cls.stat_max_space,cls.stat_counter,cls.stat_algorithm,
cls.stat_array_length,cls.stat_max_array_length,cls.stat_list_length,
int(math.log2(cls.stat_list_length)),int(cls.stat_list_length*math.log2(cls.stat_list_length)),
run_time
))
def stat_called_next_node(self):
'''
counter: should be called
if the next node funtion is called
'''
type(self)._stat_called_next_node()
@classmethod
def _stat_called_next_node(cls):
cls.stat_counter+=1
def stat_created_array(self,array):
'''
counter: should be called
after an array was created and filled
'''
type(self)._stat_created_array(array)
@classmethod
def _stat_created_array(cls,array):
cls.stat_curr_space+=len(array)
if cls.stat_curr_space> cls.stat_max_space:
cls.stat_max_space=cls.stat_curr_space
if (len(array)>cls.stat_max_array_length):
cls.stat_max_array_length=len(array)
def stat_removed_array(self,array):
'''
counter: should be called
before an array can be removed
'''
type(self)._stat_removed_array(array)
@classmethod
def _stat_removed_array(cls,array):
cls.stat_curr_space-=len(array)
@classmethod
def create_testlist(nodeclass, n):
'''
creates a single linked list of
n elements with values 1,...,n
'''
first_node=nodeclass(n,None)
for i in range(n-1,0,-1):
second_node=first_node
first_node=nodeclass(i,second_node)
return(first_node)
if __name__ == "__main__":
#cProfile.run('LinkedListNode.create_testlist(n).reverse_print()')
n=100000
ll=LinkedListNode.create_testlist(n)
LinkedListNode.do_print=False
ll.print_title()
ll.reverse_print(1)
ll.reverse_print(2)
ll.reverse_print(3)
ll.reverse_print(4)
ll.reverse_print(5)
ll.reverse_print(6)
ll.reverse_print(7)
ll.reverse_print(0)
這裏有一些結果
space maximal number of array space for
pointers to the list nodes, that
is needed
time number of times the method next_node,
that retrievs the successor of a node,
was called
alg algorithm that was selected:
0: array size is 2
1: array size is n, naive algorithm
t>1: array size is n^(1/t)
arr dimension of the arrays
sz actual maximal dimension of the arrays
n list length
log the logarithm to base 2 of n
n log n n times the logarithm to base 2 of n
seconds the runtime of the program in seconds
space time alg arr sz n log n log n seconds
100000 100000 1 100000 100000 100000 16 1660964 0.17
635 200316 2 317 318 100000 16 1660964 0.30
143 302254 3 47 48 100000 16 1660964 0.44
75 546625 4 18 19 100000 16 1660964 0.99
56 515989 5 11 12 100000 16 1660964 0.78
47 752976 6 7 8 100000 16 1660964 1.33
45 747059 7 6 7 100000 16 1660964 1.23
54 1847062 0 2 3 100000 16 1660964 3.02
和
space maximal number of array space for
pointers to the list nodes, that
is needed
time number of times the method next_node,
that retrievs the successor of a node,
was called
alg algorithm that was selected:
0: array size is 2
1: array size is n, naive algorithm
t>1: array size is n^(1/t)
arr dimension of the arrays
sz actual maximal dimension of the arrays
n list length
log the logarithm to base 2 of n
n log n n times the logarithm to base 2 of n
seconds the runtime of the program in seconds
space time alg arr sz n log n log n seconds
1000000 1000000 1 1000000 1000000 1000000 19 19931568 1.73
2001 3499499 2 1000 1001 1000000 19 19931568 7.30
302 4514700 3 100 101 1000000 19 19931568 8.58
131 4033821 4 32 33 1000000 19 19931568 5.69
84 6452300 5 16 17 1000000 19 19931568 11.04
65 7623105 6 10 11 1000000 19 19931568 13.26
59 7295952 7 8 9 1000000 19 19931568 11.07
63 21776637 0 2 3 1000000 19 19931568 34.39
如果你的代碼工作正常，但你需要想法來改進它 - 要問的最好的地方是[coderevi ew.stackexchange.com]（http://codereview.stackexchange.com） –
爲什麼你要使reverse_print成爲一個靜態方法？它的第一個參數是LinkedListNode。所以簡單地把它作爲LinkedListNode的一個方法。我也建議你在codereview上詢問。 – miracle173
算法的時間複雜度是多少？ – miracle173