己知一棵完全二叉树按顺序方式存储在数组int A1n中。设计算法求出下标分别为i和ji =nj =n的两个结点的最近的公共祖先结点的位置和值。用c语言实现并分析时间复杂度。

算法思路：

为了求出两个结点的最近公共祖先结点，需要先找到它们的共同祖先结点，然后再找到离它们最近的共同祖先结点。

对于一棵完全二叉树，可以通过下标计算出每个结点的父结点的下标。

设当前结点下标为i，则它的父结点下标为i/2（向下取整），它的左子结点下标为2i，右子结点下标为2i+1。

因此，可以从两个结点出发，分别往上找到它们的祖先结点，然后比较祖先结点是否相同，直到找到离它们最近的共同祖先结点为止。

算法实现：

时间复杂度：最坏情况下，需要向上找到根结点，因此时间复杂度为O(log n)。

代码如下：