给定M个国家和N个颜色，M大于N，每个国家一个颜色，要求相邻国家颜色不同。(1)定义存储结构类型; (2)设计算法实现上述的要求;(3)分析所设计算法的时间复杂度

(1) 定义存储结构类型：
可以使用一个二维数组或邻接矩阵来表示这个国家的颜色分配情况。如果用邻接矩阵的话，其中的矩阵A[i][j]表示第i个国家和第j个国家是否相邻，如果是则颜色相同；对于颜色信息，我们可以创建一个大小为N的数组colors，对应于每种可能的颜色。

int M, N;
bool matrix[M][M]; // 邻接矩阵
int colors[N];      // 存储颜色

(2) 设计算法实现：
一种简单的算法可以采用回溯法，从第一个国家开始，尝试给它分配每一个颜色，然后依次检查与其相邻的国家，确保它们的颜色都不相同。如果遇到无法继续的情况（即所有颜色都用过了或者有相邻国家颜色相同），就回溯到上一个位置，尝试下一个颜色。当找到一个合法的颜色分配方案时，就记录下来并结束搜索。

void backtrack(int state, int prevColor) {
    if (state == M) {
        // 如果所有国家颜色都已确定，检查是否有冲突
        for (int i = 0; i < M - 1; i++) {
            if (matrix[i][i + 1] && colors[i] == colors[i + 1]) return; // 相邻国家颜色相同，返回
        }
        // 没有冲突，找到了一个合法解
        validSolution(colors); // 将解决方案保存或输出
        return;
    }

    for (int color = 0; color < N; color++) { // 对每个颜色进行尝试
        if (color == prevColor || (!matrix[state][prevState] && colors[prevState] == color)) continue; // 避免当前颜色和前一个国家相同

        colors[state] = color; // 分配颜色
        backtrack(state + 1, color); // 继续下一位国家
    }
}

(3) 时间复杂度分析：
此算法采用的是回溯搜索策略，最坏的情况下需要尝试所有可能的颜色组合。因为每个国家都有N种颜色可以选择，而总共有M个国家，所以总的尝试次数是N^M。但是，由于存在剪枝操作（比如避免相同颜色和相邻国家），实际时间复杂度取决于是否经常触发回溯。在某些输入情况下，如果能快速排除大多数无效选择，实际时间复杂度会低于理论上的O(N^M)。然而，平均来说，如果没有其他优化条件，这仍然是一种指数级别的复杂度。